How can I prove that $T(n) = 2T(n/2) + n$ is $O(n \log n)$ ?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ The more interesting question is: How do you come up with the hypothesis? $\endgroup$– RaphaelCommented Dec 9, 2011 at 11:39
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
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.
answered Jul 29, 2011 at 8:24
$\begingroup$
$\endgroup$
2
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 )
-
-
$\begingroup$ NB:
b^(logBase(b) x) = xnote when substituting k into the general formula $\endgroup$ Commented Oct 3, 2017 at 12:40
$\begingroup$
$\endgroup$
5
Let $L(k)=T(2^k)$ and $n = 2^k$. Then $L(k)=T(n)$, $L(k-1)=T(n/2)$, and thus, $$ L(k)=2L(k-1)+2^k\tag1 $$ Multiplying $(1)$ by $2^{-k}$ gives $$ \overbrace{2^{-k}L(k)}^{a_k}=\overbrace{2^{-(k-1)}L(k-1)}^{a_{k-1}}+1\tag2 $$ Iterating $(2)$, we get $$ 2^{-k}L(k)=L(0)+k\tag3 $$ which means $$ L(k)=2^k(L(0)+k)\tag4 $$ which is $$ T(n)=n(T(1)+\log(n))\tag5 $$ Therefore, $T(n)=O(n\log(n))$.
-
$\begingroup$ This is how you come up with the hypothesis, not a proof. $\endgroup$– RaphaelCommented Dec 9, 2011 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 ♦Commented Dec 9, 2011 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 ♦Commented Dec 9, 2011 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$– RaphaelCommented Dec 10, 2011 at 11:53
-
$\begingroup$ @Raphael: I finally got brought back to this answer (9 years later). I've rewritten the iteration so it is easier to follow (without ellipses). It says the same thing, but hopefully in a more palatable manner. $\endgroup$– robjohn ♦Commented Sep 25, 2020 at 22:17
$\begingroup$
$\endgroup$
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$\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$ Commented Jul 29, 2011 at 9:45
