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 ?

Improve this question
$\endgroup$
3
  • 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, 2013 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, 2013 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, 2013 at 14:08

1 Answer 1

Reset to default
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!]

Improve this answer
$\endgroup$
2
  • $\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, 2013 at 22:11
  • 1
    $\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, 2013 at 10:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.