Master Theorem

The Master Theorem can be used to calculate the time complexity of a recurrence relation.

Recurrence relations are of the form:

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


n = number of inputs/problem

a = number of subproblems

n/b = size of each subproblem

f(n) = time to divide and combine results

The Master Theorem works only if a.f(n/b) <= c.f(n) where c<1. This is the regularity condition.

Case 1:

If f(n) = O(nlogban^{log_ba}), then T(n) = Θ\Theta(nlogban^{log_ba})

Case 2:

If f(n) = Θ\Theta(nlogban^{log_ba}), then T(n) = Θ\Theta(nlogban^{log_ba}. lg n)

Case 3:

If f(n) = Ω\Omega(nlogban^{log_ba}), then T(n) = Θ\Theta(f(n))

NOTE: The Master Theorem doesn't work for recurrence relations of the form T(n) = kT(n/k) + n.lgn because there is no polynomial difference between the recursive and function terms i.e. kT(n/k) and n.lgn respectively.

results matching ""

    No results matching ""