Master Theorem

Using The Master Theorem To Find the Big O Of Recursive Algorithms

Posted on Updated on

For some persons finding the Big O of recursive algorithms can prove to be difficult especially if the algorithms are complexed. The Master Theorem provides a relatively simple way to solve recurrence relations as long as the recurrence fits the theorem constraints.

Basic definition:
T(n) = aT(n/b) + f(nc) where a >= 1, b > 1, and c >= 1
T(n) = Θ(nc) if c >= logba
T(n) = Θ(nc log n) if c = logba
T(n) = Θ(nlogba) if c < logba

We can think of “b” as the number of branches and “a” as the number of recurrences done; lets take a look at the example.

If we have a function:

T(n) = 2T(n/1) + f(n0) : a = 1, b = 2, c = 0

log21 = 0 therefore c = logba which satisfies Θ(nclog n) = O(log n)

References:
anupcowkur.com
wikipedia.com