0
$\begingroup$

$$T(n) = 4T\left(\frac{n}{2}\right) + \frac{n^2}{\log n}$$

I have the solution here (see example 4 in that pdf), but the problem is that they have solved it by guessing. I couldn't make that guess. So if you are going to go by the guess method too, tell me how should I have made that guess?

Or, I'm actually more interested in knowing some other method that can possibly be used to solve that.

Thanks!

$\endgroup$
2
  • $\begingroup$ Looking at the file you provided, they don't solve the recurrence either, the question and the answer there are to give a big-$O$ of bound for $T(n)$. If that is what you are after, you should say so in your question. I've tagged with "asymptotics". Also the file mentions a Master Theorem which you apparently should know about (mention that as well!), so it's not pure guessing. $\endgroup$
    – Marc van Leeuwen
    Oct 2, 2012 at 5:33
  • $\begingroup$ @MarcvanLeeuwen, yes. Thank you for pointing out. Corrected :) $\endgroup$
    – GrowinMan
    Oct 2, 2012 at 5:35

1 Answer 1

Reset to default
1
$\begingroup$

$n=2^m$ and let $T(2^m) = f(m)$.

We then have \begin{align} f(m) & = 4 f(m-1) + \dfrac{4^m}m = 4 \left( 4f(m-2) + \dfrac{4^{m-1}}{m-1}\right) + \dfrac{4^m}m\\ & = 16 f(m-2) + 4^m \left( \dfrac1{m-1} + \dfrac1m \right)\\ & = 16 \left( 4f(m-3) + \dfrac{4^{m-2}}{m-2}\right) + 4^m \left( \dfrac1{m-1} + \dfrac1m \right)\\ & = 64f(m-3) + 4^m \left( \dfrac1{m-2} + \dfrac1{m-1} + \dfrac1m \right)\\ \end{align} So proceeding like this we finally get \begin{align} f(m) & = 4^{m} f(0) + 4^m \left(1+\dfrac12 + \dfrac13 + \cdots + \dfrac1m \right) \\ & \approx 4^{m} f(0) + 4^m \left(\log_e(m) + \gamma\right) \end{align} Plugging in $m = \log_2(n)$, we get $$T(n) \approx n^2 \log_e(\log_2(n)) = \mathcal{O} \left( n^2 \log(\log n)\right)$$

$\endgroup$
2
  • $\begingroup$ This is good. Is there a general rule for that kind of substitution or something? $\endgroup$
    – GrowinMan
    Oct 2, 2012 at 5:50
  • $\begingroup$ @GrowinMan Well... I don't know. In general, if you have $T(n)$ related to $T(n/k)$, take $n=k^m$ and set $f(m) = T(k^m)$. Hence, you related $f(m)$ to $f(m-1)$ and proceed. $\endgroup$
    – user17762
    Oct 2, 2012 at 5:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .