1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $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})$ $\endgroup$ – Pavel Jun 9 '16 at 5:06
  • $\begingroup$ Why isn't the answer $\theta(n \log^2 n)$? What Master Theorem are you using? $\endgroup$ – Peter Shor Jun 9 '16 at 12:30
  • $\begingroup$ @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? $\endgroup$ – Ray Jun 9 '16 at 14:31
  • $\begingroup$ 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). $\endgroup$ – Peter Shor Jun 9 '16 at 14:47
  • $\begingroup$ @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? $\endgroup$ – Ray Jun 9 '16 at 14:51
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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