Using the Akra-Bazzi Theorem to Prove Master's Theorem (CLRS)

Question

Exercise 4.7-6 of Cormen's Introduction to Algorithms asks

Use the Akra-Bazzi method to prove the continuous master theorem.

For reference, the Akra-Bazzi theorem in this textbook states that the solution of the recurrence $$T(n)=f(n)+\sum_{i=1}^k a_i T(n/b_i) $$ is $$T(n)=\Theta \left( n^p \left(1+ \int_1^n \frac{f(x)}{x^{p+1}} \mathrm{d}x \right) \right) $$ where $p$ is the unique solution of the equation $\sum_{i=1}^k a_i/{b_i}^p=1$.

The continuous master theorem is stated as follows.

Theorem 4.4 (Continuous master theorem) Let $a>0$ and $b>1$ be constants, and let $f(n)$ be a driving function that is defined and nonnegative on all sufficiently large reals. Define the algorithmic recurrence $T(n)$ on the positive real numbers by $$T(n)=aT(n/b)+f(n).$$ Then the asymptotic behavior of $T(n)$ can be characterized as follows:

1. If there exists a constant $\epsilon>0$ such that $f(n) = O(n^{\log_b a-\epsilon})$, then $T(n)=\Theta(n^{\log_b a})$.
2. If there exists a constant $k \geq 0$ such that $f(n) = \Theta(n^{\log_b a} \operatorname{lg}^k n)$, then $T(n)=\Theta(n^{\log_b a} \operatorname{lg}^{k+1} n)$.
3. If there exists a constant $\epsilon > 0$ such that $f(n) = \Omega(n^{\log_b a + \epsilon})$, and if $f(n)$ additionally satisfies the regularity condition $a f(n/b) \leq c f(n)$ for some constant $c<1$ and all sufficiently large $n$, then $T(n)=\Theta(f(n))$.

My attempt: With the setup of the continuous master theorem, the equation for Akra-Bazzi's $p$ is $a/b^p=1$, giving $p=\log_b a$. Then I tried using the complexity given by Akra-Bazzi's theorem in each case.

1. Using the Big O bound on $f$ we can bound the integral from above by a constant multiple of the constant $$\zeta(1+\epsilon)=\int_1^\infty \frac{1}{x^{1+\epsilon}} \mathrm{d}x.$$ Ignoring the constants we get the desired complexity for this case.
2. This time the integral is asymptotically tight against the integral $$\int_1^n \frac{\operatorname{lg}^k x}{x}\mathrm{d}x .$$ This again gives me the complexity needed.
3. I'm stuck here. How does the asymptotic lower bound allow me to get $f(n)$ out of this expression? I was thinking integration by parts, but that didn't go anywhere.

Would appreciate review of cases 1, 2 and advice on how to do case 3 with Akra-Bazzi. Thanks.

Answer 1

I believe the current formulation of the Akra-Bazzi theorem is insufficient to prove the third case of the continuous master theorem. For a counterexample consider the recursion $$T(n)=T(n/2)+2^n. $$ The third case of the continuous master theorem immediately gives the correct answer as $T(n)=\Theta(2^n).$ In the setting of the exercise we get $p=\log_2 1=0$, and Akra-Bazzi's theorem gives the complexity $$T(n)=\Theta \left(1+\int_1^n \frac{2^x}{x} \mathrm{d}x \right) = \Theta(1+\text{Ei}(n \log (2))-\text{Ei}(\log (2)))=\Theta\left( \frac{\mathrm{e}^{n \log2}}{n \log 2}\right) =\Theta(2^n/n), $$ where I have used the asymptotic expansion of the exponential integral function.

Looking at Wikipedia's formulation of the Akra-Bazzi theorem what appears to be missing is a "polynomial growth" condition on the driving function $f(n)$.

Answer 2

Here I generalise what was stated in the comments. We consider the product $f(n) = n^{p + \epsilon} g(n)$ where $g(n)$ is a nonnegative function that satisfies the polynomial-growth condition, e.g.: $g(n) = n^{\alpha} \lg^{\beta} n$. Plugging into Akra-Bazzi we get: $$ T(n) = n^p + n^p \int_1^n x^{\epsilon - 1} g(x) dx $$ and after applying integration by parts a few times we get for the integral: $$ \int_1^n x^{\epsilon - 1} g(x)dx = \left[ \frac{g(x)x^{\epsilon}}{\epsilon} \right]_1^n - \left[ \frac{g'(x)x^{\epsilon}}{\epsilon} \right]_1^n + \left[ \frac{g''(x)x^{\epsilon}}{\epsilon} \right]_1^n - \int_1^n x^{\epsilon - 1} g'''(x)dx$$ Derivatives reduce the degree of a polynomial so after throwing out the lower order terms we get for the recurrence: $$ T(n) = n^p + n^p \left( \frac{g(n) n^{\epsilon}}{\epsilon} - \frac{g(1)}{\epsilon} \right) $$ $$ = \Theta \left( n^{p + \epsilon} g(n) \right) = \Theta(f(n)) $$