Master theorem

For recurrences of the form T(n) = aT(n/b) + f(n), the asymptotic behavior is determined by comparing f(n) with n^(log_b a) when the theorem conditions hold.