Why does my induction proof of an algorithm's running time always seems tautological?

Question

I'm having some trouble proving algorithm's running times. The problem is not so much that I can't define the recurrence in open form nor that I cannot come to the conclusion that I know to be true. The problem is that my proofs seem rather... tautological?

Let's consider the running time for the Merge Sort algorithm:

T(2) = 1
T(n) = n + 2T(n/2)

I know the algorithm runs in O(n lg n) time, so I know I'll want to prove that

T(n) <= k n lg(n)

The induction step is proved as:

T(n+1) <= k (n+1) lg (n+1)
(n+1) + 2(n+1/2) * lg ((n+1)/2) <= k n lg(n)
n + 1 + (n+1) (lg (n+1) - 1) <= k n lg(n)
...
(n+1)lg(n+1) <= k (n+1)lg(n+1)

So far so good. Now, the problem is that if I attempt to prove that Merge Sort is O(n), the proof will still work:

T(n+1) = n+1 + 2n/2 <= kn
       = 2n + 1 <= kn (which is true)

What am I doing wrong? I've attempted similar stuff with other kinds of algorithms, such as Quick Sort and the Fibonacci sequence generation algorithm and both seem to give me the same trouble.

Thanks

Answer 1

You aren't doing the induction correctly it should be

T(n+1)=n+1 +2kn/2=(k+1)n+1 which is not less than kn

Correct proof

T(2) = 1 T(n) = n + 2T(n/2)

T(n) <= k n lg(n)

T(n+1) = n+ 2 (kn/2 lg(n/2))

= n + kn lg(n/2) < kn lg(n)