Using Master Theorem Components and Formulations

The Master Theorem is a tool that helps determine the time complexity of recurrence relation arising from divide-and-conquer algorithms. It was formulated by computer scientist Jon Bentley, and popularized by Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein in Introduction to Algorithms.

This blog post explores the Master Theorem, its components, and how it can be applied to analyze the efficiency of algorithms.

This post is my best effort. It includes notes I used to study for a challenging class. There might be mistakes in the math! If you spot an error, please let me know. I love writing these posts and want them to be the best possible! :)

🌸👋🏻 Join 10,000+ followers! Let’s take this to your inbox. You’ll receive occasional emails about whatever’s on my mind—offensive security, open source, academics, boats, software freedom, you get the idea.

Divide-and-conquer algorithms

Before discussing the Master Theorem, let’s briefly revisit divide-and-conquer algorithms.

Divide-and-conquer algorithms solve problems by breaking them into smaller, more manageable subproblems, solving each subproblem independently, and then combining the solutions to obtain the final result.

Well-known algorithms like merge sort, quicksort, and binary search are prime examples of divide-and-conquer strategies.

Merge sort illustration used on a post about recursion.

Source

Merge sort example

Recursive

Consider sorting an array using the merge sort algorithm (video). Each recursive call divides the array into two halves, sorts each half separately, and then merges them back together. This recursive decomposition captures the breaking down of a larger problem into smaller, more manageable subproblems.

	def merge_sort(arr):
	if len(arr) <= 1:
	return arr

	# split array in half
	middle = len(arr) // 2
	left_half = arr[0:middle]
	right_half = arr[middle:]

	# recursively sort each half
	left_half = merge_sort(left_half)
	right_half = merge_sort(right_half)

	# merge the sorted halves
	result = merge(left_half, right_half)
	return result

	def merge(left, right):
	result = []

	while len(left) > 0 and len(right) > 0:
	if left[0] <= right[0]:
	result.append(left[0])
	left = left[1:]
	else:
	result.append(right[0])
	right = right[1:]

	# if there are any remaining
	# elements in either left or right
	result += left
	result += right

	return result

	def main():
	arr = [12, 11, 13, 5, 6, 7]
	sorted_arr = merge_sort(arr)
	print("sorted arr:", sorted_arr)
	# sorted arr: [5, 6, 7, 11, 12, 13]

	if __name__ == "__main__":
	main()

view raw recursiveMergeSort.py hosted with ❤ by GitHub

This merge sort example demonstrates the divide and conquer paradigm by recursively dividing an array into smaller halves, independently sorting each subarray, and then merging them back together to achieve a sorted result.

However, there are multiple ways to approach this merge sort problem using divide-and-conquer.

Iterative

The divide-and-conquer paradigm does not always involve recursion; alternative strategies, such as iteration or dynamic programming, can be employed to solve subproblems and combine solutions in a non-recursive manner.

An example of the divide-and-conquer paradigm without recursion is the iterative approach to merge sort.

	def merge_sort(arr):
	n = len(arr)

	# bottom-up approach
	current_size = 1
	while current_size < n – 1:
	left_start = 0
	while left_start < n – 1:
	mid = min(left_start + current_size – 1, n – 1)
	right_end = min(left_start + 2 * current_size – 1, n – 1)

	merge(arr, left_start, mid, right_end)

	left_start += 2 * current_size

	current_size *= 2

	def merge(arr, left, mid, right):
	n1 = mid – left + 1
	n2 = right – mid

	# create temp arrays
	left_array = [0] * (n1 + 1)
	right_array = [0] * (n2 + 1)

	# copy data to temp arrays
	for i in range(n1):
	left_array[i] = arr[left + i]
	for j in range(n2):
	right_array[j] = arr[mid + j + 1]

	# merge the temp arrays
	# back into arr[left..right]
	i = j = 0
	k = left
	while i < n1 and j < n2:
	if left_array[i] <= right_array[j]:
	arr[k] = left_array[i]
	i += 1
	else:
	arr[k] = right_array[j]
	j += 1
	k += 1

	# copy the remaining elements of
	# left_array[] if there are any
	while i < n1:
	arr[k] = left_array[i]
	i += 1
	k += 1

	# copy the remaining elements of
	# right_array[] if there are any
	while j < n2:
	arr[k] = right_array[j]
	j += 1
	k += 1

view raw iterativeMergeSort.py hosted with ❤ by GitHub

In a typical divide-and-conquer fashion, the array is divided into smaller subarrays until each subarray contains only one element. However, instead of using recursive calls to merge the subarrays, an iterative approach employs a loop to repeatedly merge adjacent pairs of subarrays until the entire array is sorted. This illustrates that divide-and-conquer can be implemented without relying on recursive function calls.

Components and formulation

The Master Theorem is a tool that helps determine the time complexity of recurrence relation arising from divide-and-conquer algorithms. Say a recurrence relation takes the form:

$T(n) = aT\left(\frac{n}{b}\right) + f(n)$

The Master Theorem provides a way to solve this recurrence relation and determine the asymptotic behavior of $T(n)$ .

Here, $T(n)$ represents the time complexity of the algorithm for a problem of size $n$ , $a$ is the number of subproblems, $b$ is the factor by which the problem size is reduced, and $f(n)$ is the cost of dividing the problem and combining the results.

More math-y breakdown

$T(n) = aT\left(\frac{n}{b}\right) + f(n)$

where:

$a$ is the number of subproblems in the recursion.
$b$ is the factor by which the problem size is reduced in each recursive call.
$f(n)$ is the cost of dividing the problem and combining the results.

Master Theorem cases

The Master Theorem has three cases, each corresponding to a different relationship between $a$ , $b$ , and $f(n)$ . Let’s explore each case.

Case 1

$f(n)$ is $O(n^c)$ , where $c < \log_b{a}$

In this case, the recursive part is the dominant factor contributing to the time complexity.

The overall time complexity is:

$O(n^{\log_b{a}})$

Math-y version

$T(n) = aT\left(\frac{n}{b}\right) + f(n)$

$\text{if } f(n) = O\left(n^c\right) \text{ where } c < \log_b a$

Example

$T(n) = 2T\left(\frac{n}{2}\right) + n$

In this example, $a = 2$ , $b = 2$ , and $f(n) = n$ .

The recurrence relation falls under Case 1 because $n$ is $O\left(n^c\right)$ where $c = 1 < \log_2 2$ .

Case 2

$f(n)$ is $\Theta(n^{\log_b{a}} \log^k n)$ ,

where $k \geq 0$

Here, the recursive part and the cost of dividing and combining contribute equally to the time complexity.

The overall time complexity is:

$O(n^{\log_b{a}} \log^{k+1} n)$

Math-y version

$T(n) = aT\left(\frac{n}{b}\right) + f(n)$

$\text{if } f(n) = \Theta\left(n^{\log_b a}\right)$

Example

$T(n) = 2T\left(\frac{n}{2}\right) + n \log n$

Here, $a = 2$ , $b = 2$ , and $f(n) = n \log n$ .

The recurrence relation falls under Case 2 because $f(n)$ is:

$\Theta\left(n^{\log_2 2}\right) = \Theta(n)$ .

Case 3

$f(n)$ is $\Omega(n^c)$ , where $c > \log_b{a}$ , and $a f\left(\frac{n}{b}\right) \leq kf(n)$ for some $k < 1$ and sufficiently large $n$

In this case, the cost of dividing and combining dominates the recursive part.

The overall time complexity is $O(f(n))$ .

Math-y version

$T(n) = aT\left(\frac{n}{b}\right) + f(n)$

$\text{if } f(n) = \Omega\left(n^{\log_b a + \epsilon}\right) \text{ where } \epsilon > 0$

and

$\text{if } a f\left(\frac{n}{b}\right) \leq k f(n) \text{ for some } k < 1 \text{ and sufficiently large } n$

Example

$T(n) = 2T\left(\frac{n}{2}\right) + n^2$

In this example, $a = 2$ , $b = 2$ , and $f(n) = n^2$ .

The recurrence relation falls under Case 3 because $f(n)$ is $\Omega\left(n^{\log_2 2 + \epsilon}\right) = \Omega(n^{\epsilon})$ where $\epsilon = 1$ .

Additionally:

$a f\left(\frac{n}{b}\right) = 2 \cdot \left(\frac{n}{2}\right)^2 = \frac{1}{2}n^2 \leq k n^2$

for $k = \frac{1}{2}$ .

Application of the Master Theorem

Now, let’s illustrate the application of the Master Theorem with a classic example using merge sort. In merge sort, $a = 2$ , $b = 2$ , and $f(n) = n$ .

Thus, we can see that it falls under Case 2, resulting in a time complexity of $O(n \log n)$ .

Conclusion

In conclusion, the Master Theorem helps analyze the time complexity of divide-and-conquer algorithms. By breaking down the components and formulations of the theorem, including its three distinct cases, engineers can grasp its applicability to algorithms.

If you enjoyed this post on master theorem, consider reading Algorithm Development and Analysis.