Confusion about one of the conditions for the Akra-Bazzi method solving recurrences

135 Views Asked by At

In this paper by Akra & Bazzi, we consider linear divide-and-conquer recurrences of the form: $$u_n = \begin{cases} u_0 & n = 0 \\ \sum_{i=1}^{k} a_{i} u_{\lfloor \frac{n}{b_{i}} \rfloor} + g(n) & n \ge 1 \end{cases}$$

One of the conditions is that:

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

My problem: what does "bounded" here mean? Does it mean $\exists M: \forall x: g(x) \le M$? If so, why does this method apply to, say, the example $u_n = 2 u_{\lfloor \frac{n}{2} \rfloor} + \Theta(n \log^2\log n)$ in Section 4?

1

There are 1 best solutions below

0
On BEST ANSWER

The original Akra-Bazzi paper has many inaccuracies. A corrected/extended version is Leighton's "Notes on better master theorems for divide and conquer recurrences" (1996). Sadly, there is no "formal" reference, and the conditions of the much sharper theorem there are hard to verify. A somewhat easier to apply version is the one in Lehman, Leighton and Meyer "Mathematics for Computer Science" (this is the latest lecture notes, there is a print version by Samurai Media from 2017 (ISBN 978-9888407064). The restriction cited there is that $\lvert g'(x) \rvert$ is bounded by a polynomial in $x$.