# How do you get the upper bound over this recurrence?

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

• 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. Oct 2, 2012 at 5:33
• @MarcvanLeeuwen, yes. Thank you for pointing out. Corrected :) Oct 2, 2012 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)$$
• @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.