# Need help about solving a recurrence relation

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.

-

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

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

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

-
Thank you so much! –  bigO Mar 7 '13 at 1:14