[Solved]: Proof of big theta using induction

Problem Detail: 

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?

Asked By : Carol Doner

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32110

 Ask a Question

 Download Related Notes/Documents