How to solve the following recurrence

Question

I know others have already posted about this recurrence $T(n) = 2T(n/2) + n\lg n$ on the following these two posts: post1 and post2

However, the style in which they have solved them, is not one with which I am ery familiar. I was hoping someone could look at my work so far, and then point me in the right direction or show me what I am doing wrong. This is my work up to this point:

$$T(n) = 2T(n/2) + n\lg n$$ $$=2[2T(n/2^2) + (n/2)\lg (n/2)] + n\lg n$$ $$=2^2T(n/2^2) + n\lg(n/2)+n\lg n$$

I expanded this recurrence out a bit further and finally found the general formula:

$$2^kT(n/2^k)+n\sum_{i=0}^klg(n)-lg(2^i)$$

I understand what to set $k$ equal to in order to arrive at $T(1)$, but I honestly don't understand how to simplify the summation in this problem. Should I keep the logarithm (which is base 2 by the way) in the following format $\lg(n/2^i)$ and split the summation, or is there another way to simplify this summation? I am stuck.

EDIT

So, I made some errors in my formular when I orignally posted this. Looking at the general formula above involving $k$ now, I am still wondering how to simplify and solve it. I am not sure what to do with the $\sum_{i=0}^klg(n)$. For the $lg(2^i)$ term I am thinking I can just pull the $i$ down and pull the $lg(2) outside of the summation.

Answer 1

I agree (now) with your first three iterates, including the cancellation of the extra 2's I initially missed in my comments. I'd like for simplicity to state the general pattern I noticed in terms of beginning with $2^{k+1}T(1/2^{k+1}).$ I get $$T(n)=2^{k+1}T(1/2^{k+1})+n\ [ \lg (n)+\lg (n/2)+\lg(n/4)+ \cdots + \lg(n/2^{k}).] \tag{1}$$ The log terms inside the square brackets may be combined into a single log by using the sum of logs equal to the log of the product. For the product we have a numerator of $n^k$ since there are $k$ terms each with numerator $n$. The product of denominators is $2^0 \cdot 2^1 \cdots 2^k=2^{0+1+\cdots+k}=2^{k(k+1)/2}.$ So the sum of logs inside square brackets in $(1)$ is the single log $$\lg \frac{n^k}{2^{k(k+1)/2}}.$$ Of course since it is log base 2 one may go one more step to $k \lg n -[k(k+1)/2]$ but I don't see much advantage in that.

Answer 2

There is another closely related recurrence that admits an exact solution. Suppose we have $T(0)=0$ and $T(1)=1$ and for $n\ge 2$ $$T(n) = 2 T(\lfloor n/2 \rfloor) + n \lfloor\log_2 n\rfloor.$$

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

Then we can unroll the recurrence to obtain the following exact formula for $n\ge 1$ $$T(n) = 2^{\lfloor \log_2 n \rfloor} + \sum_{j=0}^{\lfloor \log_2 n \rfloor} 2^j (\lfloor \log_2 n \rfloor - j) \left( \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j} \right).$$

Now to get an upper bound consider a string of one digits which yields $$T(n) \le 2^{\lfloor \log_2 n \rfloor} + \sum_{j=0}^{\lfloor \log_2 n \rfloor} (\lfloor \log_2 n \rfloor - j) \left( \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^k \right).$$

Note that this bound is attained and cannot be improved. It simplifies to $$\lfloor \log_2 n \rfloor^2 2^{\lfloor \log_2 n \rfloor} + \lfloor \log_2 n \rfloor 2^{\lfloor \log_2 n \rfloor} - 2^{\lfloor \log_2 n \rfloor} + \lfloor \log_2 n \rfloor + 2.$$

The lower bound is for the case of a one digit followed by a string of zeros and yields $$T(n) \ge 2^{\lfloor \log_2 n \rfloor} + 2^{\lfloor \log_2 n \rfloor} \times \sum_{j=0}^{\lfloor \log_2 n \rfloor} (\lfloor \log_2 n \rfloor - j),$$ which simplifies to $$\frac{1}{2} \lfloor \log_2 n \rfloor^2 2^{\lfloor \log_2 n \rfloor} + \frac{1}{2} \lfloor \log_2 n \rfloor 2^{\lfloor \log_2 n \rfloor} + 2^{\lfloor \log_2 n \rfloor}.$$

Joining the dominant terms of the upper and the lower bound we obtain the asymptotics $$\lfloor \log_2 n \rfloor^2 2^{\lfloor \log_2 n \rfloor} \in \Theta\left(\log^2 n \times 2^{\log_2 n}\right) = \Theta\left(n \log^2 n\right).$$

This MSE link points to additional calculations of this type.