How to give a good guess to the recurrence relation problem

Question

I have been trying to solve the following recurrence relation

$$T(n)=2T(\frac{n}{2}) + nlgn$$ by using substitution method.

I started to compute $T(1)$ ,$T(4)$,$T(8)$,$T(16)$ to guess a solution as below:

$$T(1)=1$$ $$T(2)=2+2lg2=4$$ $$T(4)=8+8lg2=16$$ $$T(8)=32+24lg2=56$$ $$T(16)=112+64lg2=176$$

My guess is that $T(n)$ should be something like $nlg^2n$ but I couldn't get a correct term.

Can anyone improve my guess?

Answer 1

At each step, we replace $n$ with $n/2$ and multiply the equation by $2$: \begin{align*} T(n) - 2T(\tfrac{n}{2}) &= n\lg n \\ 2T(\tfrac{n}{2}) - 2^2T(\tfrac{n}{2^2}) &= n\lg \tfrac{n}{2} \\ 2^2T(\tfrac{n}{2^2}) - 2^3T(\tfrac{n}{2^3}) &= n\lg \tfrac{n}{2^2} \\ 2^3T(\tfrac{n}{2^3}) - 2^4T(\tfrac{n}{2^4}) &= n\lg \tfrac{n}{2^3} \\ &~~\vdots \\ 2^{\lg n - 1}T(2) - 2^{\lg n}T(1) &= n\lg2 \\ \end{align*} Summing the $\lg n$ equations together, we note that the LHS telescopes, yielding: \begin{align*} T(n) - 2^{\lg n}T(1) &= n\sum_{k=0}^{\lg n - 1} \lg \tfrac{n}{2^k} \\ T(n) - n \cdot 1 &= n\sum_{k=0}^{\lg n - 1} (\lg n - k) \\ T(n) - n &= n\sum_{k=0}^{\lg n - 1}\lg n - n\sum_{k=0}^{\lg n - 1} k \\ T(n) - n &= n(\lg n)(\lg n) - n\frac{(\lg n)(\lg n - 1)}{2} \\ T(n) &= \frac{1}{2}n\lg^2 n + \frac{1}{2}n \lg n + n \end{align*} Thus, we conclude that $T(n) = \Theta(n \lg^2 n)$, which you suspected.

Answer 2

Take $n = 2^kp$ where $p$ is odd, then $$T(2^{k+1}p) = 2T(2^kp) + 2^{k}p\log(2^kp) $$

So $$\dfrac{T(2^{k+1}p)}{2^{k+1}} = \dfrac{T(2^kp)}{2^k} + \dfrac{pk\log(2)+p\log p }{2}$$

Then we have $$\dfrac{T(2^{k+1}p)}{2^{k+1}} = T(p) + \dfrac{p\log2}{2}(\sum_{j=0}^k j) + \frac{p(k+1)\log p}{2}$$

$$T(2^{k+1}p) = 2^{k+1}T(p) + 2^k p \log2\dfrac{(k+1)k}{2} + p(k+1)(\log p)2^k$$

If you plug $p=1$, this can be simplified a bit

Answer 3

In $T(n)=2T(\frac{n}{2}) + n\ lgn$ put $n=2^m$. This becomes $T(2^m) =2T(2^{m-1})+m 2^m $.

(Note: I fixed an error so the following has been completely rewritten.)

Let $S(m) =T(2^m) $. Then $S(m) =2S(m-1)+m2^m $. Dividing by $2^m$, $2^{-m}S(m) =2^{-m-1}S(m-1)+m $. Letting $U(m) =2^{-m}S(m) $, $U(m) =U(m-1)+m $ or $U(m)-U(m-1) =m $. Summing, $U(m) =m(m-1)/2 \approx m^2/2 $.

Working back, $S(m) =2^mU(m) \approx 2^mm^2/2 $. Finally, $T(n) =S(lg\ n) \approx n (lg\ n)^2/2 $.

Answer 4

with Mathematica we get this here $\left\{\left\{a(n)\to 2 c_1 n-n \log \left(n^{\frac{1}{2} \left(-\frac{\log (n)}{\log (2)}-1\right)}\right)\right\}\right\}$

Answer 5

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_2 n \rfloor} d_k 2^k.$$

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

Note that this formula produces matching values for the data at $n=2^j$ posted by the OP in the question, namely the sequence $$1, 4, 16, 56, 176, 512, 1408, 3712\ldots$$

Now to get an upper bound consider a string of one digits to obtain $$T(n) \le 2^{\lfloor \log_2 n \rfloor} + \sum_{j=0}^{\lfloor \log_2 n \rfloor -1} (\lfloor \log_2 n \rfloor - j) \times \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^k.$$ This 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.$$

This bound is actually attained and cannot be improved upon, just like the lower bound, which occurs with a one digit followed by zeroes to give $$T(n) \ge 2^{\lfloor \log_2 n \rfloor} + \sum_{j=0}^{\lfloor \log_2 n \rfloor -1} (\lfloor \log_2 n \rfloor - j) \times 2^{\lfloor \log_2 n \rfloor}.$$

This 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 \times 2^{\lfloor \log_2 n \rfloor} \in \Theta\left((\log_2 n)^2 \times 2^{\log_2 n}\right) = \Theta\left((\log n)^2 \times n\right).$$

The above would seem to be in agreement with what the Master theorem would produce.

There are some additional calculations using this method at this MSE link.