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.
T(n) = aT(n/b) + f(nc) where a >= 1, b > 1, and c >= 0
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:
a = 1, b = 2, c = 0 (logba)
T(n) = 2T(n/1) + f(n0)
c = 0 which satisfies Θ(nclog n) = O(log n)