12
$\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$

1 Answer 1

6
$\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$
5
  • 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$
    – RajS
    May 14, 2016 at 12:05
  • $\begingroup$ @anir - Use equality $\log_2(\frac{n}{2^k}) = \log_2 n - k$ $\endgroup$
    – HEKTO
    May 14, 2016 at 15:36
  • 1
    $\begingroup$ I still didn't get how that series collapses to $\Theta(n)$ :'¬( Math-noob-here... $\endgroup$
    – RajS
    May 19, 2016 at 18:42
  • $\begingroup$ @anir - I'll expand my answer $\endgroup$
    – HEKTO
    May 19, 2016 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$ Jul 15, 2017 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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