Masters Theorem
The recurrence T(n) = aT(n/b) + f(n) can be solved as follows.
For all large enough n,
\(If a ⋅ f(n /b) ≤ αf(n )\) for some \(α < 1\), then \(T(n ) = O( f(n ))\)
If a ⋅ f(n /b) ≥ βf(n ) for some β > 1, then \(T(n ) = O(a^{\log_{b}n} )\)
If a ⋅ f(n /b) = f(n ) then \(T(n ) = Θ( f(n) \log_{b}n )\)
