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