Need help about solving a recurrence relation

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.