What’s wrong with the following induction proof?

Question

For $n = 2^i$ which is a power of 2, we might define \begin{equation} T(n) = \left\{ \begin{array}{lr} 2 \cdot T(\frac{n}{2}) + 32 \cdot n & n > 2 \\ 2 & n = 2 \end{array} \right. \end{equation}

The following wrong proof shows $T(n) = O(n\log{(n)}).$ I want to know what is the error.

• Inductive Hypothesis: $T(n) = O(n\log{(n)}).$
  
• Base case: $T(2) = 2 = O(1) = O(2log(2))$
  
• Inductive Step:
  
  • Suppose that $T(n) = O(nlog(n))$ for $n < k$.
  • Then $T(k) = 2 \cdot T(\frac{k}{2}) + 32 \cdot k$ by definition
  • So $T(k) = 2 \cdot O(\frac{k}{2} \log(\frac{k}{2})) + 32 \cdot k$ by induction
  • But that’s $T(k) = O(k\log(k))$ for all n, so the I.H. holds for $n = k.$
    
• Conclusion:
  
  • By induction, $T(n) = O(n\log{(n)})$ for all n.

Answer 1

When doing an induction proof of a big-oh result, you have to assume that a particular constant works for $n$ and show that the same constant works for $n+1$.

In this case, you have to show that $T(n) < c n \log(n)$ implies $T(n+1) < c (n+1) \log(n+1)$.

Work this through and see what condition $c$ must satisfy. If you get a contradiction, then the big-oh condition does not hold.