9
$\begingroup$

I was solving recurrence relations. The first recurrence relation was

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

The solution of this one can be found by Master Theorem or the recurrence tree method. The recurrence tree would be something like this:

![enter image description here

The solution would be:

$T(n)=\underbrace{n+n+n+...+n}_{\log_2{n}=k \text{ times}}=\Theta(n \log{n})$

Next I faced following problem:

$T(n)=2T(n/2)+\log{n}$

My book shows that by the master theorem or even by some substitution approach, this recurrence has the solution $\Theta(n)$. It has same structure as above tree with the only difference that at each call it performs $\log{n}$ work. However I am not able to use same above approach to this problem.

$\endgroup$
5
$\begingroup$

The non-recursive term of the recurrence relation is the work to merge solutions of subproblems. The level $k$ of your (binary) recurrence tree contains $2^k$ subproblems with size $\frac {n}{2^k}$, so you need at first to find the total work on the level $k$ and then to summarize this work over all the tree levels.

For example, if the work is constant $C$, then the total work on the level $k$ will be $2^k \cdot C$, and the total time $T(n)$ will be given by the following sum:

$$T(n) = \sum_{k=1}^{\log_2{n}}2^k C = C(2^{\log_2{n}+1}-2) = \Theta(n)$$

However, if the work logarithmically grows with the problem size you'll need to accurately compute the solution. The series would be like the following:

$$T(n)=\log_2{n}+\underbrace{2\log_2(\frac {n} {2})+4\log_2(\frac {n} {4})+8\log_2(\frac {n} {8}) + ....}_{\log_2{n} \text{ times}}$$

It'll be a quite complex sum:

$$T(n)=\log_2{n}+\sum_{k=1}^{\log_2{n}}2^k \log_2(\frac {n} {2^k})$$

I'll temporarily denote $m=\log_2{n}$ and simplify the summation above:

$$\sum_{k=1}^{m}2^k \log_2(\frac {n} {2^k})=\\=\sum_{k=1}^{m}2^k(\log_2{n}-k)=\\=\log_2{n}\sum_{k=1}^{m}2^k-\sum_{k=1}^{m}k2^k=\\=\log_2{n}(2^{m+1}-2)-(m2^{m+1}-2^{m+1}+2)$$

Here I used a formula for the $\sum_{k=1}^{m}k2^k$ sum from the Wolfram|Alpha online symbolic algebra calculator. Then we need to replace $m$ back by $\log_2{n}$:

$$T(n)=\log_2{n}+2n\log_2{n}-2\log_2{n}-2n\log_2{n}+2n-2$$ $$=2n-\log_2{n}-2=\Theta(n)$$

Q.E.D.

$\endgroup$
  • 1
    $\begingroup$ damn I made super stupid mistake in asking question. Now corrected. However now am not able to get how the stuff cancel each other in the series: $2^0\log_2\frac{n}{2^0}+2^1\log_2\frac{n}{2^1}+2^2\log_2\frac{n}{2^2}+...+2^{ \log_2{n}}\log_2\frac{n}{2^{ \log_2{n}}}=\log_2{n}+2\log_2{\frac{n}{2}}+4\log_2{\frac{n}{4}}+...+n\log_2{1}$.. This is the series that you come up with right? Trying with $n=8$, I got $\log_2{8}+2\log_2{4}+4\log_2{2}+8\log_2{1}=3+4+4=11$. Whats wrong here? $\endgroup$ – anir May 14 '16 at 12:05
  • $\begingroup$ @anir - Use equality $\log_2(\frac{n}{2^k}) = \log_2 n - k$ $\endgroup$ – HEKTO May 14 '16 at 15:36
  • 1
    $\begingroup$ I still didn't get how that series collapses to $\Theta(n)$ :'¬( Math-noob-here... $\endgroup$ – anir May 19 '16 at 18:42
  • $\begingroup$ @anir - I'll expand my answer $\endgroup$ – HEKTO May 19 '16 at 22:43
  • $\begingroup$ @HEKTO If you solve above equ of comment, you still get nlog(n) ?? I have tried a lot. would you please help me here ? $\endgroup$ – roottraveller Jul 15 '17 at 17:15

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.