# 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 )\)