This post was originally written on Codeforces; relevant discussion can be found here.

Motivation

On a computer science discord server, someone recently asked the following question:

Is the master theorem applicable for the following recurrence? \(T(n) = 7T(\lfloor n / 20 \rfloor) + 2T(\lfloor n / 8 \rfloor) + n\)

There was some discussion related to how \(T\) is monotonically increasing (which is hard to prove), and then someone claimed that there is a solution using induction for a better bound. However, these ad hoc solutions often require some guessing and the Master theorem is not directly applicable.

Similarly, in the linear time median finding algorithm (or the linear time order statistics algorithm in general), the recurrence is \(T(n) = T(\lfloor 7n/10 \rfloor + \varepsilon) + T(\lfloor n/5 \rfloor) + n\) where \(\varepsilon \in \Theta(1)\) Also, in merge sort and creating a segment tree recursively, the time complexities are \(T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + f(n)\) where \(f(n)\) is \(\Theta(n)\) for merge sort and \(\Theta(1)\) for segment tree construction.

Even the general form of the recurrence that the master theorem handles is just \(T(n) = aT(n/b) + f(n)\), and it doesn’t handle cases of the form \(T(n) = aT(\lfloor n/b \rfloor) + f(n)\) and \(T(n) = aT(\lceil n/b \rceil) + f(n)\), which is what we find in a lot of algorithms.

To cleanly handle all these cases at once, there is a generalization of the Master theorem for recurrences, called the Akra-Bazzi theorem. It is not really well-known, and since it is not trivial to prove (the proof is pretty nice, I recommend looking at it), it is often skipped over in CS courses on algorithms (sometimes even the instructors are not aware of this theorem). This is why I wanted to write this post — to provide a better way of reasoning about your divide and conquer algorithms.

Statement

Theorem: Consider \(T(x)\) given by a sufficient number of base cases (for instance, bounded for \(x < x_0\) for \(x_0\) defined later), and defined recursively by \(T(x) = g(x) + \sum_{i=1}^k a_i T(b_i x + h_i(x))\) for large enough \(x\) (i.e., for all \(x \ge x_0\) for some \(x_0\)).

Then, subject to the following conditions:

  • \(a_i > 0\) and \(0 < b_i < 1\) are constants for each \(i\)
  • \(g\) is differentiable and \(|g’(x)|\) has at most polynomial growth (i.e., \(|g’(x)| \in O(x^c)\) for some constant \(c\))
  • \(|h_i(x)| \in O(x/(\log x)^2)\) for all \(i\)

We have, if \(p\) is the unique solution to \(\sum_{i=1}^k a_i b_i^p = 1\), then

\[ T(x) \in \Theta \left(x^p \left(1 + \int_{1}^{x} \frac{g(u)}{u^{p+1}} \mathrm{d}u \right)\right) \]

There are some more pedantic conditions on \(x_0\) and \(g\) for this to hold, but for all practical purposes, those conditions (like some definite integrals with finite upper and lower limits are finite) are true. For more, you can refer to this paper.

Advantages and applications

This has the following advantages:

  • Being much more general than the master theorem, and in different cases for \(p\), reduces to the master theorem readily.
  • Being applicable to more back-of-the-envelope calculations and more CS-like recurrences, where you don’t want to think about floors/ceils/constant offsets — the “error term” \(h_i\) takes care of that for you.
  • Reduces your dependence on ad hoc methods like guess-and-induct.

Let’s apply this theorem to the few examples mentioned above (although there won’t be any non-trivial results among the above examples, an important special case will be illustrated in the following examples).

  • The original recurrence: \(T(n) = 7T(\lfloor n / 20 \rfloor) + 2T(\lfloor n / 8 \rfloor) + n\) — note that in this case, we get \(0 < p < 1\). The theorem claims that \(T(n) \in \Theta(x^p (1 + \frac{x^{1-p} - 1}{1-p})) = \Theta(x)\).
  • The same analysis as above holds for the linear-time median finding algorithm.
  • For the merge sort recurrence and the segment tree building recurrence, we have \(p = 1\). The theorem allows us to use the Master theorem directly without caring about the floors.

A nice exercise could be to try analyzing the complexity of the brute force in this problem.