# Finding recurrence when Master Theorem fails

Following method is explained by my senior. I want to know whether I can use it in all cases or not. When I solve it manually, I come to same answer.

$T(n)= 4T(n/2) + \frac{n^2}{\lg n}$

In above recurrence master theorem fails. But he gave me this solution, when

for $T(n) = aT(n/b) + \Theta(n^d \lg^kn)$

if $d = \log_b a$

if $k\geq0$ then $T(n)=\Theta(n^d \lg^{k+1})$

if $k=-1$ then $T(n)=\Theta(n^d\lg\lg n)$

if $k<-1$ then $T(n)=\Theta(n^{\log_ba})$

using above formulae, the recurrence is solved to $\Theta(n^2\lg\lg n)$. When I solved manually, I come up with same answer. If it is some standard method, what it is called ?

• See also our reference question for solving recurrences. In particular, the first case you have been given is covered by the master theorem. But then, even the Akra-Bazzi method does not cover your example. Oh well. By manually, do you mean using recursion trees?
– Raphael
Apr 2, 2013 at 19:16
• ^yes. Basically I meant without using Master Theorem or Akra-Bazi method. Here's one solution : chuck.ferzle.com/Notes/Notes/DiscreteMath/…
– avi
Apr 3, 2013 at 12:38
• I see; that would be guess & proof, then. Legit, but arduous: you need to deal with lower and upper bound separately and perform induction proofs for both.
– Raphael
Apr 3, 2013 at 14:08

OK, try Akra-Bazzi (even if Raphael thinks it doesn't apply...) $$T(n) = 4 T(n / 2) + n^2 / \lg n$$ We have $g(n) = n^2 / \ln n = O(n^2)$, check. We have that there is a single $a_1 = 4$, $b_1 = 1 / 2$, which checks out. Assuming that the $n / 2$ is really $\lfloor n / 2 \rfloor$ and/or $\lceil n / 2 \rceil$, the implied $h_i(n)$ also check out. So we need: $$a_1 b_1^p = 4 \cdot (1 / 2)^p = 1$$ Thus $p = 2$, and: $$T(n) = \Theta\left(n^2 \left( 1 + \int_2^n \frac{u^2 du}{u^3 \ln u} \right) \right) = \Theta\left(n^2 \left( 1 + \int_2^n \frac{du}{u \ln u} \right) \right) = \Theta(n^2 \ln \ln n)$$ (The integral as given with lower limit 1 diverges, but the lower limit should be the $n_0$ for which the recurrence starts being valid, the difference will usually just be a constant, so using 1 or $n_0$ won't make a difference; check the original paper.)
• Ah, so you are allowed/supposed to change the lower boundary of the integral -- that was my problem exactly! Your explanation does not make a lot of sense to me, though: the integral does not converge on $[1,2]$, so the difference it not a constant! I guess I'll have to look at the paper at some point... if only it was readily available.