2025-02-04 -- the master theorem
--------------------------------

This is a generalized form of the master theorem. I learned
it in the winter term of 2023/2024 from Raimund Seidel and
Karl Bringmann. I find this form easier to understand than
the Wikipedia article.

Suppose you have a divide-and-conquer algorithm whose running
time you can express with the following recurrence relation:

T(n) <= c_0                                      if n <= n_0,
T(n) <= a * T(ceil(n/b) + r) + c * n^d * log^s n if n > n_0.

You can freely pick a, b, c, c_0, d, n_0, r, s as constants
from [0, infinity).

Then:

T(n) is in O(n^d * log^s n)     if a < b^d,
T(n) is in O(n^d * log^(s+1) n) if a = b^d,
T(n) is in O(n^(log_b a))       if a > b^d.

Super useful. Put this on your cheat sheet.