5
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ StoogeSort is a fun one to write a recurrence for (using T(2n/3) ) and to get a runtime for, but it's not an example of a useful "real word" algorithm $\endgroup$
    – JimN
    Sep 10, 2020 at 23:37
  • $\begingroup$ I accepted an answer, but I'd still love to hear other examples if anyone has them. $\endgroup$
    – Adam Smith
    Sep 23, 2020 at 21:16

1 Answer 1

4
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.