Master theorem
In the analysis of algorithms, the master theorem provides a cookbook solution in asymptotic terms (using Big O notation) for recurrence relations that occur in many divide and conquer algorithms. It was introduced and popularized by Introduction to Algorithms.
Examples with common algorithms
| Algorithm | Recurrence | Big-Oh Solution |
|---|---|---|
| Binary Search | T(n) = T(n/2) + O(1) | O(log n) |
| tree traversal | T(n) = 2 T(n/2) + O(1) | O(n) |
| Mergesort | T(n) = 2 T(n/2) + O(n) | O(n log n) |