5
$\begingroup$

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 ?

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Raphael Apr 2 '13 at 19:16
  • $\begingroup$ ^yes. Basically I meant without using Master Theorem or Akra-Bazi method. Here's one solution : chuck.ferzle.com/Notes/Notes/DiscreteMath/… $\endgroup$ – avi Apr 3 '13 at 12:38
  • $\begingroup$ 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. $\endgroup$ – Raphael Apr 3 '13 at 14:08
5
$\begingroup$

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

[I've taken the liberty to add this to the Akra-Bazzi examples in the reference question, thanks!]

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Raphael Apr 2 '13 at 22:11
  • $\begingroup$ I checked the original paper and found some differences to your version. See my edit on the reference answer and comments there. $\endgroup$ – Raphael Apr 3 '13 at 10:59

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.