Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a recurrence relation which is like the following:

$$ T(n) = 2T(n/2) + \log_2 n. $$

I am using recursion tree method to solve this. And at the end, i came up with the following equation:

$$ T(n)=(2\log_2 n)(n-1)-(1*2 + 2*2^2 + \ldots + k*2^k) $$ where $k=\log_2 n$.

I am trying to find a theta notation for this equation. But i cannot find a closed formula for the sum $$ 1*2 + 2*2^2 + \ldots + k*2^k.$$

How can i find a big theta notation for $T(n)$?

Thanks.

share|improve this question

3 Answers 3

up vote 3 down vote accepted

$$T(n) = 2 T(n/2) + \log_2(n)$$ Let $n=2^m$ and $T(2^m) = g(m)$. Then the recurrence can be rewritten as \begin{align} g(m) & = 2g(m-1) + m\\ & = 2(2g(m-2) + m-1) + m\\ & = 4g(m-2) + 2(m-1) + m\\ & = 4(2g(m-3) + m-2) + 2(m-1) + m\\ & = 8g(m-3) + 4(m-2) + 2(m-1) + m\\ & = 16 g(m-4) + 8(m-3) + 4(m-2) + 2(m-1) + m \end{align} Hence, by induction, we have \begin{align} g(m) & = 2^m g(0) + \sum_{k=1}^m 2^{m-k}k = 2^m g(0) + 2^m \sum_{k=1}^m \dfrac{k}{2^k}\\ & = 2^m g(0) + 2^m \left(2 - \dfrac{m+2}{2^m}\right) = 2^m(2+g(0)) - (m+2) \end{align} where $$\sum_{k=1}^m kx^k = x \dfrac{d}{dx}\left(\sum_{k=0}^m x^k\right) = x \dfrac{dx}{dx} \left(\dfrac{1-x^{m+1}}{1-x}\right) = x \cdot \left(\dfrac{mx^{m+1} - (m+1)x^m+1}{(1-x)^2} \right)$$ Hence, $$T(n) = (2+T(1))n - (2+\log_2(n))$$

share|improve this answer
    
@julien One obvious check, why your solution is incorrect and why mine is possibly correct, is to plug in $n=1$. In my solution, I get $T(1) = T(1)$, where as in yours, you get $T(1) = T(1) - 2$, which is obviously incorrect. –  user17762 Mar 7 '13 at 0:50
    
Ok, I did my homework and I actually find the same solution as yours. Sorry again. –  1015 Mar 7 '13 at 0:59
    
Thank you so much! –  bigO Mar 7 '13 at 1:14

As observed by Marvis, the sequence $x_m=T(2^m)$ satisfies the first order linear recurrence formula $$ x_m=2x_{m-1}+m. $$ The homogeneous equation $x_m=2x_{m-1}$ has general solution $x_m=C2^m$. This can be checked by induction, but it follows easily from the general theory of homogeneous linear recurrence sequences.

Since the non homogeneous part is a degree $1$ polynomial, we look for a particular solution of the form $x_m=Am+B$. This is called the method of undetermined coefficients. Plugging this is the formula yields $$ Am+B=2(A(m-1)+B)+m. $$ So we get a solution if we take $A=-1$ and $B=-2$. Namely $x_m=-m-2$.

Finally, the general solution is the sum of the general homogeneous solution and the particular solution, namely $x_m=C2^m-m-2$. Making $m=0$ yields $x_0=C-2$ so $$ x_m=(x_0+2)2^m-m-2. $$

Going back to $T(n)$, this can be expressed as $$ T(n)=(T(1)+2)n-\log_2n -2 $$ for all powers of $2$.

share|improve this answer
    
Thank you so much! –  bigO Mar 7 '13 at 1:13

Let $T(0)=0$ and let the recurrence relation be $$ T(n) = 2 T(n/2) + \lfloor \log_2 n \rfloor.$$

Furthermore let the binary representation of $n$ be $$ n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$

Then it is not difficult to see that $$ T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} 2^j (\lfloor \log_2 n \rfloor-j) = \lfloor \log_2 n \rfloor \sum_{j=0}^{\lfloor \log_2 n \rfloor} 2^j - \sum_{j=0}^{\lfloor \log_2 n \rfloor} 2^j j = 2^{\lfloor \log_2 n \rfloor+1} -\lfloor \log_2 n \rfloor - 2.$$ This formula holds for all $n$ and not just powers of two.

This recurrence is so simple it does not depend on the actual values of the bits that form $n$, but only on their number. Simplifying, we obtain $$ T(n) = 2^{\lfloor \log_2 n \rfloor+1}-\lfloor \log_2 n \rfloor - 2 \in \Theta(n).$$

This procedure is employed in a somewhat more sophisticated manner at the following link.

share|improve this answer
    
Thank you so much! –  bigO Mar 7 '13 at 1:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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