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

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

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)

• Hi. I thought I could take any "k" on the left side of the equation out, as taking it out or letting the "k" on the right side be as large as possible would be equivalent? Other way of stating this question is: should I then also have to put "k_1", "k_2", etc parameters on all the terms of the question? Commented Sep 2, 2015 at 0:41
• no it should be the same k Commented Sep 2, 2015 at 0:44
• Another related question, then: should then I have to state that T(n) <= (k1 n) lg (k2 n) ? Commented Sep 2, 2015 at 0:45
• No it should be the same k. so k1=k2. Commented Sep 2, 2015 at 0:47
• Could you further explain why? It's not that I don't take your word for it, but I'd like to understand how this works. To start off: should it be "k n lg n" or "k n lg kn" ? Commented Sep 2, 2015 at 0:48