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)