Data structures and algorithms

The master theorem

Solves the divide-and-conquer recurrences that turn up in every algorithms interview.

T(n) = a\,T\!\left(\tfrac{n}{b}\right) + f(n) \ \Rightarrow\ \text{compare } f(n) \text{ with } n^{\log_b a}

Where

$f(n) = \Theta(n^{\log_b a})$: The tied case: multiply by $\log n$ .
$a = b = 2,\ f = \Theta(n)$: Merge sort: $\Theta(n\log n)$ .

Assumptions

Regularity conditions apply in the unbalanced cases; the tied case is the one that turns up.

Sanity check. Binary search is $a = 1$ , $b = 2$ , $f = \Theta(1)$ , giving $\Theta(\log n)$ .

Where this is taught

Complexity: reading it off, and deriving it · CS · Complexity