Looking for good Master Theorem examples

Question

I'm teaching an Algorithms class (junior/senior level), and we've just proved the validity of the Master Theorem. I'd like some good questions on it, both for homeworks and for exam questions. Problem is, most questions I've seen online seem to just give the constants (e.g. a=2, b=2, c=1, now solve for the Θ class), which isn't very intellectually challenging.

So what are some real-world recursive algorithms whose running times can be analyzed with the Master Theorem? I have a very limited list already:

• Merge sort (possibly quick sort too, but that's a little problematic)
• Binary search
• Traversing a balanced binary tree
• Ternary search (finding the max of a unimodal function)

Anything else?

Answer 1

A famous example is Strassen's matrix multiplication algorithm, whose running time satisfies the recurrence $T(n) = 7T(n/2) + O(n^2)$. A similar example is Karatsuba's algorithm for fast integer multiplication, whose running time satisfies the recurrence $T(n) = 3T(n/2) + O(n)$. Other algorithms for multiplying matrices or integers supply even more examples of this sort.

The running time of the median-of-medians linear time selection algorithm satisfies the recurrence $T(n) = T(0.2n) + T(0.7n) + O(n)$, which might be too challenging to analyze.

FFT is a classical example of an extremely useful divide-and-conquer algorithm, whose running time satisfies the recurrence $T(n) = 2T(n/2) + O(n)$.