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.
Complexity 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).
Cost
- Space
- O(1)
Before this
Related
Taught by the same lesson
Complexity in Numbers covers these too, in the same run.