5
$\begingroup$

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

  • 0
    The more interesting question is: How do you come up with the hypothesis?2011-12-09

5 Answers 5

1

Use the Master Theorem.

4

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.

3

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

  • 0
    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.2011-12-10
3

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 )

  • 0
    NB: `b^(logBase(b) x) = x ` note when substituting k into the general formula2017-10-03
1

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.

  • 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.2011-07-29