Master Theorem
Compare f(n) with n^(log_b a), the leaf count of the recursion tree, to read off T(n) in three cases.
Decision · step 2 of 7Complexity in Numbers: The master theorem on five recurrences
binary search: a = 1, b = 2, f(n) = 1. Leaves: n^(log_2 1) = 1. f(n) matches the leaf count, so every level costs about the same and there are log n levels: T(n) = Theta(log n).
What you will see
Slide a, b and f(n); the recursion tree's per-level costs show which case dominates.
Cost
| Space | O(1) |
|---|
How you work with it here
explore, compare two runs, run it on your own input.
Screen readers: Growth curves are described in words and as a table of operation counts for sample input sizes; each concept has a one-sentence spoken definition.
Reduced motion: Curves and counters update without animation.
Before this
Related
Taught by the same lesson
Complexity in Numbers covers these too, in the same run.