<p>A famous example is <a href="https://en.wikipedia.org/wiki/Strassen_algorithm" rel="nofollow noreferrer">Strassen's matrix multiplication algorithm</a>, whose running time satisfies the recurrence <span class="math-container">$T(n) = 7T(n/2) + O(n^2)$</span>. A similar example is <a href="https://en.wikipedia.org/wiki/Karatsuba_algorithm" rel="nofollow noreferrer">Karatsuba's algorithm</a> for fast integer multiplication, whose running time satisfies the recurrence <span class="math-container">$T(n) = 3T(n/2) + O(n)$</span>. Other algorithms for multiplying matrices or integers supply even more examples of this sort.</p>
<p>The running time of the median-of-medians <a href="https://en.wikipedia.org/wiki/Median_of_medians" rel="nofollow noreferrer">linear time selection algorithm</a> satisfies the recurrence <span class="math-container">$T(n) = T(0.2n) + T(0.7n) + O(n)$</span>, which might be too challenging to analyze.</p>
<p>FFT is a classical example of an extremely useful divide-and-conquer algorithm, whose running time satisfies the recurrence <span class="math-container">$T(n) = 2T(n/2) + O(n)$</span>.</p>

CC BY-SA 4.0
2020-09-10T22:31:06.217Z
2020-09-10T22:31:06.217Z
Yuval Filmus
<p>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.</p>
<p>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:</p>
<ul>
<li>Merge sort (possibly quick sort too, but that's a little problematic)</li>
<li>Binary search</li>
<li>Traversing a balanced binary tree</li>
<li>Ternary search (finding the max of a unimodal function)</li>
</ul>
<p>Anything else?</p>

CC BY-SA 4.0
2020-09-10T23:37:46.577Z
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
JimN
CC BY-SA 4.0
2020-09-23T21:16:38.003Z
I accepted an answer, but I'd still love to hear other examples if anyone has them.
Adam Smith
<undergraduate><algorithms><exercises><recursion>
Looking for good Master Theorem examples
# Looking for good Master Theorem examples

(Asked by: username_0 on 2020-09-10)

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?

**Tags:** undergraduate, algorithms, exercises, recursion

> **Comments:**
> **username_1**: 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  
> **username_0**: I accepted an answer, but I'd still love to hear other examples if anyone has them.  

---

## 1 answers

### Answer by username_2 on 2020-09-10. Score: 4 | Accepted answer

A famous example is [Strassen's matrix multiplication algorithm](https://en.wikipedia.org/wiki/Strassen_algorithm), whose running time satisfies the recurrence $T(n) = 7T(n/2) + O(n^2)$. A similar example is [Karatsuba's algorithm](https://en.wikipedia.org/wiki/Karatsuba_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](https://en.wikipedia.org/wiki/Median_of_medians) 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)$.


---

