2025-02-05 -- the akra-bazzi theorem
------------------------------------

This is the Akra-Bazzi theorem. I learned it in the winter
term of 2024/2025 from Raimund Seidel. The form I give here
is copied from Wikipedia.

Suppose you have a divide-and-conquer algorithm for which
the master theorem does not work and whose running time you
can express with a recurrence relation like the following:

T(n) = g(n) + a_i * T(b_i * n + h_i(n)) for n >= n_0.

Repeat the right summand (with varying i) as needed.
n_0, a_i, b_i are constants. g and h_i are there for
perturbations. Conditions:

- a_i > 0,
- 0 < b_i < 1,
- |g'(n)| is in O(n^c) for some c,
- |h_i(n)| is in O(n / log^2 n).

Then:

- Find p such that the sum over all (a_i * b_i^p) is 1.
- Integrate g(x) / x^(p+1) from 1 to n.
- T(n) is in Theta(n^p * (1 + integral)).