Akra-Bazzi method integral diverges

Question

I want to solve this recursion:

$$T(n) = 5T(\frac{n}{5}) + \frac{n}{lg(n)}$$

My attempt and issue:

None of the cases for master theorem apply here. I tried using Akra-Bazzi method (https://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method) with

$f(n) = \frac{n}{lg(n)}$

The derivative of $f(n)$ satisfies the condition for Akra-Bazzi: $$\frac{d}{dn} f(n) = \frac{1}{lg(n)} - \frac{1}{ln(2)*lg^2(n)} = O(n)$$ Also I found that $p=1$ to satisfy the method's condition that $\frac{a}{b^p} = 1$.

Now the solution is given by this formula:

$$T(n) = \theta(n^p*(1-\int_{1}^{n} \frac{f(x)}{x^{p+1}} dx)$$

So I calculated the integral: $$\int\frac{f(x)}{x^{p+1}} dx = lg(lg(x)) + C$$, but with one of the limits being $1$ it diverges!

The weird thing is that according to Wolfram Alpha calculator, $T(n) = \theta(nlg(lg(n)))$.

So why is it true if the integral diverges? What am I getting wrong here?

Answer 1

Your recurrence isn't really defined for $n = 1$. This suggests using a different value for the lower bound in the integral. The formula given by Akra–Bazzi doesn't actually depend on the exact value of the lower bound that you choose – it can at most affect the big Theta constant or, in your case, some lower order term. If you choose any lower bound which is large enough, then the Akra–Bazzi formula gives you $\Theta(n\log\log n)$ as wanted.