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

Taught in

References