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

Improve this question
$\endgroup$
6
  • $\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, 2016 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, 2016 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$
    – oilimeDev
    Jun 9, 2016 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, 2016 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$
    – oilimeDev
    Jun 9, 2016 at 14:51

2 Answers 2

Reset to default
2
$\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.

Improve this answer
$\endgroup$
2
$\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.)

Improve this answer
$\endgroup$

Your Answer

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

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