8
$\begingroup$

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

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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).

$\endgroup$
4
  • $\begingroup$ This seems to be comment, not an answer? Am I missing something? $\endgroup$
    – Raphael
    Feb 10, 2020 at 14:14
  • 1
    $\begingroup$ Shamelessly plugging my own work: I verified a variant of Leighton's version of the theorem in a proof assistant. There are some issues with Leighton's note, but if I recall correctly, the theorem itself was correct as stated. For details, see my paper: doi.org/10.1007/s10817-016-9378-0 Free preprint version available here: www21.in.tum.de/~eberlm/pdfs/divide_and_conquer_isabelle.pdf $\endgroup$ Jun 23, 2020 at 13:25
  • 1
    $\begingroup$ Note that my version indeed requires the integral to exist on all compact intervals with sufficiently large boundaries, and it requires $g$ to be bounded on any such interval. These are very mild restrictions. $\endgroup$ Jun 23, 2020 at 13:30
  • $\begingroup$ I recommend that paper of Manuel Eberl, Proving Divide and Conquer Complexities in Isabelle/HOL. $\endgroup$
    – John L.
    Oct 4, 2022 at 22:33

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.