Why does Akra-Bazzi need that toll-function g is bounded?

Question

Following up on vonbrand's answer I want to write a small document about stronger master theorems for our students, one of which is the Akra-Bazzi theorem. I have copied the theorem from their paper [1] and found -- besides a small notational confusion² -- the following problem.

The authors require (emphasis mine):

$g(x)$ is defined for real values $x$, and is bounded, positive and nondecreasing function $\forall x \geq 0$

Here, $g$ is the toll function, that is the recurrence has the form

$\qquad\displaystyle T(n) = g(n) + \sum_{i=1}^k a_i T\bigl(\lfloor n b_i^{-1} \rfloor\bigr)$.

Now, at the end of their paper (p209) they give multiple examples for applying their result and they use functions in $\Omega(n)$ which are clearly not bounded.

From skimming the proof they mainly seem to require that integrals of the form

$\qquad\displaystyle \int_a^b \frac{g(x)}{x^{p+1}} dx$

have finite values. So, requiring $g$ to be bounded on every compact interval might be sufficient; I did not work through the proof in detail. Is it possible they mean that?

My question is: How should the Akra-Bazzi theorem be stated so that it is consistent with proof and examples?

---

1. On the solution of linear recurrence equations by M. Akra and L. Bazzi (1998)
2. They require $a_i \in R^{*+}$. Is this some notation I don't know, or a typo? I assume the intended meaning is $(0,\infty) \subseteq \mathbb{R}$.

Answer 1

Take a look at Tom Leighton's notes, referenced from the Wikipedia article. His notes apparently have less typos then the original paper. The condition he demands of $g$ is having polynomial growth, which means that if you scale the argument by a constant, then the amount that the function scales is also bounded by a constant.

Answer 2

Nicest version of the Akra-Bazzi theorem I've seen is the one in Lehman, Leighton, Meyer "Mathematics for Computer Science", the discussion starts at page 1019. An (older) print version is available. No proof, though. Would need to slough through Leighton's note to verify that the lecture notes/book version is right (it has somewhat different conditions, that are much easier to check).