master theorem
A ready-made rule that solves recurrences of the form T(n) = aT(n/b) + f(n) by comparing f(n) with n raised to log base b of a.
In more detail
For merge sort, a = 2 and b = 2 give n^1, which matches f(n) = n, so T(n) is O(n log n). For binary search, a = 1 and b = 2 give n^0 = 1, matching f(n) = 1, so T(n) is O(log n). It saves working out a recursion tree by hand.
Related terms
- recurrence relation — An equation that defines an algorithm's cost on input size n in terms of its cost on smaller inputs, such as T(n) = 2T(n/2) + n.
- divide and conquer — A problem-solving technique that splits a problem into independent smaller pieces, solves each recursively, and combines their answers.
Taught in
- Divide And Conquer And The Recurrence — Algorithms & Data Structures for Working Engineers