# Proof of big theta using induction [duplicate]

This question already has an answer here:

Here is a recursive definition for the runtime of some unspecified function. $a$ and $c$ are positive constants.

$T(n) = a$, if $n = 2$

$T(n) = 2T(n/2) + cn$ if $n > 2$ Use induction to prove that $T(n) = \Theta(n \log n)$

Any idea on how to solve this?

## marked as duplicate by FrankW, David Richerby, Yuval Filmus, Rick Decker, Patrick87Oct 20 '14 at 17:32

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• Why not use the Master theorem? since $n^{log_2(2)} = n = f(n)$, you can state that $T(n) \in \Theta(n.log(n))$ – Smajl Oct 20 '14 at 6:51
• Because is says to use induction. – Carol Doner Oct 20 '14 at 23:03

## 1 Answer

Hint: If $T(n/2) \leq M \frac{n}{2} \log \frac{n}{2}$ then $$T(n) = 2T(n/2) + cn \leq Mn\log \frac{n}{2} + cn \leq Mn\log n +n (c-M\log 2).$$ The lower bound should be similar.

• Then can we assume that n(c-Mlog2) gets more and more negligible as n gets larger and larger, thus the Big Oh part of the proof is done? Or I should include more calculations for this? – Carol Doner Oct 20 '14 at 22:55
• No, a proof doesn't work this way. For the induction to work you really need to prove that $T(n) \leq Mn\log n$. – Yuval Filmus Oct 21 '14 at 2:53