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

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?

• On the solution of linear recurrence equations by M. Akra and L. Bazzi (1998)

• 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}$.

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.

StackExchange Computer Science Q#17916, answer score: 5