# Solving the recurrence T(n) = 4T(n/4) + n log n with the iterative method

I'm trying to solve

$$T(n) = 4T(n/4) + n \log_{10}n.$$

I'm having trouble with Iteration Method near the end. As far as I went, I obtained the General Formula as:

$$4^kT(n/4^k)+n\log n+\sum (n/4^k)\log(n/4^k)$$

And trying to get the moment when it finishes iterating:

$$(n/4^k)=1$$ $$n=4^k$$ $$\log_4n=k$$

And here I get stuck. I know I have to substitute $k$ with $\log_4n$ but after that I'm lost. Can I get a bit of help with explanation of every step?

Here are some more details:

Swapped $\log_4n$ on all $k$: $$4^{\log_4n} T(n/4^{\log_4n})+n\log_2n+\sum_{n=0}^{\log_4n}n\log n$$

From logarithm rules of $a^{log_an} = n$, it ends like this: $$(n)(1)+n\log_2n+\sum_{n=0}^{\log_4n}n\log n$$

I'm not sure how to express the sum in $n$, but as you can see already, it is $O(n\log_2n)$, and with the Master Theorem, you obtain the same result $O(n\log n)$.

• $T(n)=n(log_4n+log_4n/4+log_4n/16+...+log_41)$ (assuming that $T(1)=0$). $log_4\frac{n}{k}=log_4n-log_4k$, so you get: $n(nlog_4n-1-2-3-...-n)=n(nlog_4n-(\frac{n(1+n)}{2}))=n^2log_4n-(\frac{(n^2+n^3)}{2})$ Jun 9, 2016 at 5:06
• Why isn't the answer $\theta(n \log^2 n)$? What Master Theorem are you using? Jun 9, 2016 at 12:30
• @PeterShor I used the Generic Form, but I never did an exercises with $f(n)=nlogn$ so I might be wrong. Can you elaborate on your result to find any mistakes on my side? Jun 9, 2016 at 14:31
• Okay, I've googled the Master Theorem. Wikipedia is correct, but not well-written enough to be easy to understand. The next five references I checked all have statements of the theorem that don't even treat this case. So your confusion is totally justified; look at the Wikipedia article (or a textbook that covers this case). Jun 9, 2016 at 14:47
• @PeterShor found a related question here, where I assumed nlogn would be (1) but it doesn't grow as fast as $n^c$, so Master Theorem can't be applied, is it correct? Jun 9, 2016 at 14:51

As a practical method, assume "log" is the base 2 logarithm (if not, that's just a constant factor), and calculate T (2^20):

$T (2^{20}) = 20 · 2^{20} + 4 T (2^{18})$ $= 20 · 2^{20} + 18 · 2^{20} + 16 T (2^{16})$ $= 20 · 2^{20} + 18 · 2^{20} + 16 · 2^{20} + 64 T (2^{14})$ ... $= (20+18+16+...+2) · 2^{20} + 2^{20} · T (1)$

So $T (n) ≈ n ((log n)^2 / 4 + T (1))$

Now you can play around with that result to get the exact recursion.

Your "General Formula" is incorrect. The third term (with the sum) is incorrect. It should be $n$ rather than $n/4^k$.

Make the suitable correction through the rest of your answer, and use the fact that

$$\sum_{k=0}^{\log_4 n} n \log_{10}(n/4^k) \le \sum_{k=0}^{\log_4 n} n \log_{10} n$$

and you should be able to get an upper bound from there. (The final sum is easy to evaluate as every term is the same.)