5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The more interesting question is: How do you come up with the hypothesis? $\endgroup$ – Raphael Dec 9 '11 at 11:39
1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ @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. $\endgroup$ – Srivatsan Jul 29 '11 at 9:45
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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))$.

$\endgroup$
  • $\begingroup$ This is how you come up with the hypothesis, not a proof. $\endgroup$ – Raphael Dec 9 '11 at 11:37
  • $\begingroup$ @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$. $\endgroup$ – robjohn Dec 9 '11 at 17:41
  • $\begingroup$ @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. $\endgroup$ – robjohn Dec 9 '11 at 17:41
  • $\begingroup$ 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. $\endgroup$ – Raphael Dec 10 '11 at 11:53
3
$\begingroup$

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 )

$\endgroup$
  • $\begingroup$ nice analysis ....thanks $\endgroup$ – Sudip Das Dec 8 '15 at 15:37
  • $\begingroup$ NB: b^(logBase(b) x) = x note when substituting k into the general formula $\endgroup$ – Theophilus Omoregbee Oct 3 '17 at 12:40
1
$\begingroup$

Use the Master Theorem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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