Master Theorem Solver

Solve recurrence relations of the form T(n) = aT(n/b) + f(n)

Input Parameters

a (number of subproblems):

b (factor by which problem size is reduced):

f(n) (cost at each level):

n (problem size):

The Master Theorem provides a solution to recurrence relations of the form:

T(n) = aT(n/b) + f(n)

If f(n) = O(n^(log_b(a) - ε)) for some ε > 0, then T(n) = Θ(n^(log_b(a)))

If f(n) = Θ(n^(log_b(a)) * log^k(n)) for some k ≥ 0, then T(n) = Θ(n^(log_b(a)) * log^(k+1)(n))

If f(n) = Ω(n^(log_b(a) + ε)) for some ε > 0, and af(n/b) ≤ cf(n) for some c < 1, then T(n) = Θ(f(n))