The Master Theorem

Master Theorem: $T(n) = aT(n/b) + f(n)$

Let $c = \log_b a$:

$1.$ If $f(n) = O(n^{c-\epsilon})$: $T(n) = \Theta(n^c)$

$2.$ If $f(n) = \Theta(n^c)$: $T(n) = \Theta(n^c \log n)$

$3.$ If $f(n) = \Omega(n^{c+\epsilon})$: $T(n) = \Theta(f(n))$

Merge sort: $2T(n/2) + n$. $a=2,b=2,c=1,f=n$. Case 2: $\Theta(n \log n)$. Binary search: $T(n/2) + 1$. $a=1,b=2,c=0,f=1$. Case 2: $\Theta(\log n)$.