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