Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How can I prove that $T(n) = 2T(n/2) + n$ is $O(n \log n)$ ?

share|improve this question
    
The more interesting question is: How do you come up with the hypothesis? –  Raphael Dec 9 '11 at 11:39
add comment

5 Answers

up vote 1 down vote accepted

There are two ideas to do this. The first one is telescoping where you recursively use the definition of $T(n)$ or you could of course use induction (this almost always works). For a sketch of the proof check page 3 here. Note that here it is assumed that $n$ is a power of 2 making the proof simpler, if not it goes in the same fashion nevertheless.

share|improve this answer
2  
@Dan If, for some reason, you could solve the recurrence for $n$ a power of two, but couldn't solve it for a general $n$, then you can do the following. Let $n'$ be the power of two such that $n \leq n' < 2n$. Then $T(n) \leq T(n') = O(n' \log n') = O(2n \log (2n)) = O(n \log n)$. The constant hidden by the $O$ notation is slightly worse, but that's fine. –  Srivatsan Jul 29 '11 at 9:45
add comment

HINT:

Use induction to show that there are constants $c$ and $n_0$ s.t. $T(n) \leq c \cdot n \log n \quad\forall n \geq n_0$. Use $T(2)$ as your base case. Remember cool log properties to reduce the logarithm and to use the induction hypothesis.

Post your progress if you get stuck.

share|improve this answer
add comment

Let $L(k)=T(2^k)$ and $n = 2^k$. Then $L(k)=T(n)$, $L(k-1)=T(n/2)$, and $L(k)=2L(k-1)+2^k$. Thus, $$ \begin{align} L(1) &= 2\;L(0) + 2^1 \\ L(2) &= 2\;L(1) + 2^2 \\ &= (2^2\;L(0) + 2^2) +2^2 \\ L(3) &= 2\;L(2) + 2^3 \\ &= (2^3\;L(0)+2^3+2^3)+2^3 \\ L(4) &= 2\;L(3) + 2^4 \\ &= (2^4\;L(0)+2^4+2^4+2^4)+2^4 \\ &\dots \\ L(k) &= 2^k\;L(0) + k\;2^k \\ &\text{or}\\ T(n) &= n\;T(1) + \log_2(n)\;n \\ &\text{when }n\text{ is a power of }2 \end{align} $$ Therefore, $T(n)=O(n\log(n))$.

share|improve this answer
    
This is how you come up with the hypothesis, not a proof. –  Raphael Dec 9 '11 at 11:37
    
@Raphael: Above, it is shown that $L(k)=2^kL(0)+k\;2^k$. That is, $L(k)=O(k2^k)$. Unfortunately, the hypothesis only allows us to compute $T(n)$ for $n=m2^k$, for some $m$. The argument above works for any $m$ (I chose $m=1$, but for a different $m$, only the big-O constant needs to be adjusted). Therefore, the result above for $n=2^k$ is essentially all we can infer. Hopefully, there are some other assumptions, such as monotonicity, which can be used to extend the estimate above to all values of $n$. –  robjohn Dec 9 '11 at 17:41
    
@Raphael: Perhaps you are worried about the free-form induction. Sometimes free-form induction is easier to follow, and gets the idea across more clearly. The point of a proof is to convince the reader that the statement being proven is true, and I hope that that is accomplished above. –  robjohn Dec 9 '11 at 17:41
    
That is indeed my problem with such "proofs". The expressiveness of $\dots$ heavily depends on the reader. Also, they can be "used" to hide bugs. In this particular case, an induction is probably even shorter than your pattern-guessing steps; of course, you'd need both. –  Raphael Dec 10 '11 at 11:53
add comment

Use the Master Theorem.

share|improve this answer
add comment

T(1) = 1

T(n) = 2T (n/2) + cn

T(n) = 2T (n/2) + cn

T(n/2) = 2T(n/4) + c (n/2)

T(n) = 2 [ 2T (n/4) + c (n/2) ] + cn

T(n) = 4T (n/4) + 2cn

Similary, T(n) = 8T (n/8) + 3cn

General T(n) = 2^k T (n/2^K) + kcn

(n/2^k) = 1

n = 2^k

k = log base2 n

plug in k into the general formula

T(n) = n T(1) + logBase2n cn

T(n) = Big Thetha(n log n )

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.