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 Mnlog frac{n}{2} + cn leq Mnlog n +n (c-Mlog 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
