Master Theorem

Math for CS · Axiom Academy

Solve divide-and-conquer recurrences by inspection The Master theorem applies to recurrences of the form: where (number of subproblems), b > 1 (factor by which the problem shrinks), and f(n) is the work done outside the recursive calls. The key quantity is — this is the exponent of the number of leaves in the recursion tree. We compare the growth of f(n) against . Case 1 (Leaf-heavy): If for some , then Case 3 (Root-heavy): If for some , and for some c < 1 (regularity condition), then Think of it as a competition between the leaves ( total leaf work) and the root ( f(n) work at the top level): Case 1: Leaves grow polynomially faster than f(n) → leaves dominate Case 2: Leaves and root are the same order → each of the levels contributes equally Case 3: f(n) grows polynomially faster than the leaf count → root dominates T(n) = 2T(n/2) + n . Here a=2, b=2 , so . f(n) = n^2 = O(n^ 2.807 - 0.807 ) → Case 1 : . T(n) = T(n/2) + O(1) . Here a=1, b=2 , so . T(n) = 2T(n/2) + n^2 . Here a=2, b=2 , so . *The median-of-medians Select algorithm doesn't fit the Master theorem form (two different-sized subproblems). Use substitution instead. The Master theorem does not apply when: f(n) falls in the "gap" between cases — e.g., (not polynomially smaller, but not either) The subproblems have different sizes: T(n) = T(n/3) + T(2n/3) + n The number of subproblems depends on n : The regularity condition in Case 3 fails The Master theorem solves T(n) = aT(n/b) + f(n) by comparing f(n) to

This is the written version of the interactive lesson above. See the full Math for CS course.