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


  • $\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 '12 at 5:33
  • $\begingroup$ @MarcvanLeeuwen, yes. Thank you for pointing out. Corrected :) $\endgroup$ – GrowinMan Oct 2 '12 at 5:35

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

| cite | improve this answer | |
  • $\begingroup$ This is good. Is there a general rule for that kind of substitution or something? $\endgroup$ – GrowinMan Oct 2 '12 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 '12 at 5:54

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.