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)


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s