AlgoScope

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 analysis, analysis, advanced
binary search: case 2, T of n is log n.abf(n)leafcaseT(n)binmrgkarstrn^212112log n
binary search: case 2, T of n is log n.abf(n)leafcaseT(n)binmrgkarstrn^212112log n

Complexity in Numbers: The master theorem on five recurrences

Decision, step 2 of 7

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).

How complexity in numbers works

Cost

Space
O(1)

Taught by the same lesson

Complexity in Numbers covers these too, in the same run.