I have seen a few examples of using the master theorem on this to obtain O(n*log^2(n)) as an answer. I am trying to solve this by unrolling and solving the summation, but I can't seem to get the same answer. My steps are below.

Given $T(1) = 1$, $T(2) = 1$ (Time taken is constant in these two cases)

I noticed that by unrolling a few times: $$T(n) = 2\left[2T\left(\frac{n}{4}\right)+\frac{n}{2}\log{\frac{n}{2}}\right] + n\log n$$ $$T(n) = 2^{2}T\left(\frac{n}{2^{2}}\right)+n \log{\frac{n}{2}} + n\log n$$ $$T(n) = 2^{2}\left[2T(\frac{n}{8})+\frac{n}{2}\log{\frac{n}{4}}\right]+n \log{\frac{n}{2}} + n\log n$$ $$T(n) = 2^{3}T\left(\frac{n}{8}\right)+2n\log{\frac{n}{4}}+n \log{\frac{n}{2}} + n\log n$$

This looks like it follows $$T(n) = \underbrace{2^{k}T\left(\frac{n}{2^k}\right) + 2^{k}n\log\left(\frac{n}{2^{k+1}}\right)}_{\log_2n \text{ times}}$$

I use the fact that $\frac{n}{2^k} = 1$, so $k = \log_2n$. Substituting this in: $2^{k}T(\frac{n}{2^k})$ = $2^{\log_2n}T(1) = n$

Doing this summation as: $$T(n)=n + n\log_2{n}+\sum_{k=0}^{\log_2{n}-1}2^{k} n \log_2\left(\frac {n} {2^{k+1}}\right)$$ $$T(n)=n + n\log_2{n}+n\sum_{k=0}^{\log_2{n}-1}2^{k} \log_2\left(\frac {n} {2^{k+1}}\right)$$ $$T(n)=n + n\log_2{n}+n\sum_{k=0}^{\log_2{n}-1}2^{k} \log_2(n-k+1)$$

This is where I get stuck, I have a feeling I messed something up somewhere and it is making this summation much harder to solve, but I am not sure where. Where did I go wrong?


1 Answer 1


First, you can get the the result from the second xase of master theorem. Second, you have a mistake in your exapnsion:

$$T(n) = 2T(\frac{n}{2}) + n\log(n) = 2(2T(\frac{n}{2^2} + \frac{n}{2}\log(\frac{n}{2})) + n\log(n) = n\log(n) + n\log(\frac{n}{2}) + 2^2T(\frac{n}{2^2}) = n\log(n) + n\log(\frac{n}{2}) + 2^2(2T(\frac{n}{2^3} + \frac{n}{2^2}\log(\frac{n}{2^2})) = n\log(n) + n\log(\frac{n}{2}) + n \log(\frac{n}{2^2}) + 2^3T(\frac{n}{2^3})$$

Hence, we will have the following, if we suppose $T(1) = 0$, w.l.o.g:

$$T(n) = \sum_{i=0}^{\log(n)}n\log(\frac{n}{2^i}) = n \log(\Pi_{i=0}^{\log(n)}\frac{n}{2^i}) = n \log(\frac{n^{\log{n}}}{2^{\frac{\log(n) \times (\log(n) + 1)}{2}}}) = n \log(n) \log(\frac{n}{\sqrt{2}\sqrt{n}}) = n \log(n)\log{\frac{\sqrt{n}}{\sqrt{2}}} = \Theta(n \log^2(n))$$

Be aware that, if we change the values of $T(1)$ and $T(2)$ to the given constant values, nothing changed in the asymptotic analysis.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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