What Is The Master Theorem?

The Master Theorem is a recurrence relation solver that is a very helpful tool to use when evaluating the performance of recursive algorithms. Using The Master Theorem, we can easily deduce the Big-O complexity of divide-and-conquer algorithms.

Recurrence Relations

A recurrence relation is a type of equation where each element depends on a previous outcome of the equation. A good example of a recurrence relation is the fibonacci sequence:

<div style="width:100%;text-align:center;font-size:24px;font-style:italic;"> F<sub>n</sub> = F<sub>n - 1</sub> + F<sub>n - 2</sub> </div>

When we write code in such a way, it typically makes use of recursion to allow a function to call itself over and over again.

Assumptions

Before we dive in further, it'll help to familiarize yourself with the following concepts:

The Master Theorem

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/Alg_MasterThm_01.png" alt="master theorem formula." style="max-width:95%;width:500px;"> </div>

The general form of the master theorem is as follows:

<div style="width:100%;text-align:center;font-size:24px;font-style:italic;"> T(n) = aT(n / b)+ O(n<sup>d</sup>) </div>

Let's break down what each variable represents:

  • n / b: this represents the number of sub-problems that an algorithm breaks into each iteration. For example, Merge Sort divides an array into two halves until the array only has one item before reconstructing the array. Therefore it would be represented as n/2.
  • aT(..): while b represents the number of sub-problems that are divided into, a represents the number of sub problems that the algorithm will use. This is important as some algorithms divide a problem into three pieces, but may only operate on two of them. Binary search also utilizes this idea to make itself efficient.
  • O(n<sup>d</sup>): The final part of the theorem states the amount of work that is done by the algorithm at each iteration. Mainly, it comes in the form of what work is done during the conquer portion when the solution is being assembled from the pieces.

Once you have a, b, and d, we plug the numbers into the equation and hold onto the result, T(n). With the result, we'll take a look at the system of equations in the above image. If we once again plug our numbers into the 3 comparisons on the right-side column, we'll notice only one of those comparisons are true. With the true comparison, the answer to the equation is the result of plugging our numbers into the corresponding Big-O equation on the left-side column.

The end result of this theorem is the upper bound of an algorithms execution time, represented in Big-O notation.

Examples

Merge Sort

<a href="https://www.devmaking.com/learn/algorithms/merge-sort/" target="_blank" style="color:inherit">Merge Sort</a> works to sort an array by dividing it into "left" and "right" halves recursively until only one element remains in each sub list. Once that has been achieved, the left and right arrays are "merged" back together in sorted order. Taking it step by step for each variable:

  • We divide the array in half each time; b = 2.
  • Once the arrays have been divided, both halves are reassembled in sorted order; a = 2.
  • When "merging" the arrays, we need to look at every element; O(n), d = 1.

Representing this by the master theorem results in T(n) = 2T(n/2) + O(n).

When we plug these numbers into the equation:

<div style="width:100%;text-align:center;font-style:italic;font-size:150%;">d ? log<sub>b</sub>a</div> It equates to the following:

<div style="width:100%;text-align:center;font-style:italic;font-size:150%;">1 = log<sub>2</sub>2</div> Therefore, by matching the system, we know that the correct formula is:

<div style="width:100%;text-align:center;font-style:italic;font-size:150%;">n<sup>d</sup>log<sub>b</sub>n = n<sup>1</sup>log<sub>2</sub>n</div> Which evaluates to a final result of:

<div style="width:100%;text-align:center;font-style:italic;font-size:150%;">O(n log n)&#8718;</div>

<a href="https://www.devmaking.com/learn/algorithms/binary-search/" target="_blank" style="color:inherit">Binary search</a> is a diminish and conquer algorithm that takes advantage of the master theorem properties to find a specific number in a sorted structure. It works by finding the midpoint of a list; if the number being looked for is higher, the bottom half of the list is discarded. The same is true in the opposite case. This occurs until the number is discovered and returned. Taking this step by step:

  • We jump to the midpoint of the remaining array each iteration; b = 2.
  • We discard the half of the array that does not contain the value; a = 1.
  • Once the value is found, it is returned and no more work is done. O(1), d = 0.

This results in T(n) = (1)T(n/2) + O(1).

Plugging this into the equation results in 0 = log<sub>2</sub>1.

Using the corresponding formula yields:

<div style="width:100%;text-align:center;font-style:italic;font-size:150%;">n<sup>d</sup>log<sub>b</sub>n = n<sup>0</sup>log<sub>2</sub>n</sup></div> Which evaluates to a final result of:

<div style="width:100%;text-align:center;font-style:italic;font-size:150%;">O(log n)&#8718;</div> <br>

> Challenge: If a recurrence relation results in a tree structure where the depth has at most 2<sup>d</sup> leaves, and a decision tree of size n has at most n! leaves, find the lower bound for sorting algorithms in Big-O notation!

Further Resources