My Awesome CSC148 SLOG: The Master Theorem

The Master Theorem

When doing various sorting algorithms in class, we talked a little about the order of an algorithm. Some of these analyses were straightforward, such as selection sort and insertion sort. But other sorting algorithms such as merge sort and quicksort are harder to analyze due to their recursive structure. When analyzing the runtime of recursive functions, we are often faces with a recursive identity that we need to solve. The master theorem provides a solution to many of these recurrences.

Lets say the following is our function:

def T(n):

if n>1:

f(n) operations done here

T(n/b)

..... called a times .....

T(n/b)

The recurrence formula for this method will be: (a & b constants, a >= 1, b > 1)

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

Now the master theorem says that:

If $f(n) = \Theta\left( n^{c} \right)$ where $c < \log_b a$ , then $T(n) = \Theta\left( n^{\log_b a} \right)$
If $f(n) = \Theta\left( n^{c} \log^{k} n \right)$ where $c = \log_b a$ then $T(n) = \Theta\left( n^{c} \log^{k+1} n \right)$
If $f(n) = \Theta\left( n^{c} \right)$ where $c > \log_b a$ then $T\left(n \right) = \Theta\left(f(n) \right)$

When faced with one of the above cases, the master theorem provides a mechanical way to solve the recurrence.