Master Theorem

Introduction and Background

• The Master Theorem is a powerful tool in the field of computer science, specifically in the analysis of algorithms. It is used to determine the time complexity of recursive algorithms, particularly those which follow a ‘divide and conquer’ approach¹².

• In divide and conquer algorithms, a problem is broken down into several smaller subproblems of the same type. These smaller problems are then solved independently and the solutions are combined to solve the original problem. Recursion is a common principle in such algorithms. Typical examples of divide and conquer algorithms include the binary search, merge sort, and quick sort algorithms³.

• The Master Theorem provides a systematic method to calculate the time complexity of such divide and conquer algorithms. It can immediately give the time complexity in terms of Big O notation, thus providing a simple way to predict the efficiency of the algorithm³⁴.

• The theorem was first presented in the textbook “Introduction to Algorithms” by Cormen, Leiserson, Rivest, and Stein¹. Since then, it has remained an integral part of the study of algorithms due to its practical use in analyzing the time complexity of recursive functions²³⁴.

Methodology and Results

Divide and conquer algorithm

Divide and conquer algorithm is a problem-solving method that decomposes a problem into several smaller, structurally similar subproblems, solves these subproblems recursively, and then merges their solutions to obtain the solution to the original problem.

How to set up recursive relations

The overall idea for solving the problem is to establish a recurrence relation. Through the recurrence relation, the problem can be decomposed into smaller subproblems, and the solution to the original problem can be ultimately obtained.

Recurrence relations are usually represented in mathematical form, where T(n) represents the time taken to process an input of size n.

• Base Case: When the problem size is a small constant, the processing time is usually constant, represented as Θ(1). This is the basic termination condition for recursion.

• Recursive Case: When the problem size exceeds the base case, the recurrence relation consists of two parts:

  • aT(n/b): Represents the time taken to process a total of a subproblems of size n/b recursively.
  • fdiv(n): Represents the time taken for the divide step, i.e., decomposing the problem into subproblems.
  • fcomb(n): Represents the time taken for the combine step, i.e., merging the solutions of subproblems.

• Meanings of Parameters:

  • In aT(n/b), a represents the number of subproblems after decomposition, and T(n/b) represents the time taken to process a single subproblem.
  • fdiv(n) represents the time taken for the divide step, usually related to the problem size n.
  • fcomb(n) represents the time taken for the combine step, also usually related to the problem size n.

• Recurrence Relation:

  • The entire recurrence relation describes the process of decomposition, processing, and merging of the problem, as well as the time consumed by each step.

The divide and conquer algorithm and recursive relations

• The relationship between the divide and conquer algorithm and recursive relations is closely intertwined. The divide and conquer algorithm is a method of breaking down a problem into smaller subproblems and recursively solving them. In the divide and conquer algorithm, the original problem is decomposed into multiple subproblems, and then the final solution is obtained by recursively solving these subproblems.

• Recursive relations describe the relationship between the size of the problem and its solution. In the divide and conquer algorithm, recursive relations are used to represent the process of decomposing the problem into subproblems and to calculate the time and resources required to solve these subproblems. Recursive relations are typically expressed in recursive form, where the size of the problem is a function of the size of the problem itself.

• By solving recursive relations, we can determine the time and space complexity of the divide and conquer algorithm. Through analyzing recursive relations, we can understand how the size of the problem decreases with each recursion and determine the time and space consumption of each recursive step. This helps us evaluate the efficiency of the algorithm and provides guidance for solving the problem.

• Therefore, the relationship between the divide and conquer algorithm and recursive relations is that the divide and conquer algorithm solves the original problem by recursively solving subproblems, and recursive relations are used to describe the relationship between the size of the problem and its solution.

Expansion Method (Standard Method)

Expansion method is a commonly used approach for solving recursive relations. It decomposes the problem into smaller subproblems by expanding the recursive relations multiple times, and gradually obtains the solution to the original problem.

• Step 1: Expansion of Recursive Relations
  Firstly, expand the recursive relations to obtain the solution for each subproblem, and express them in the form of recursive expressions.
• Step 2: Construction of Recurrence Tree
  Construct a recurrence tree with the expanded recursive expressions, where each level of the tree represents a different recursion level, and each node represents a solution to a subproblem.
• Step 3: Solving the Recurrence Tree
  Analyze and solve the recurrence tree to obtain the analytical solution or recurrence relation of the problem, thereby determining the algorithm’s time complexity.
• Step 4: Verification
  Finally, verify whether the obtained time complexity satisfies the original recursive relations to ensure the correctness of the analytical solution.

Examples of merge sort and maximum subarray problem

• Algorithm Concept

  • Divide the original array into two subarrays, solve the maximum subarray problem for each subarray separately, and then merge them to obtain the maximum subarray of the original array.
  • The problem can be recursively solved until the size of the array is small enough to be solved directly.

• Process of Divide and Conquer Algorithm

  • Divide: Divide the original array into two subarrays and solve the maximum subarray problem for each subarray separately.
  • Combine: Merge the maximum subarrays of the left and right subarrays to obtain the maximum subarray across the middle position.
  • Recurrence: Recursively solve the maximum subarray problem for the left and right subarrays until the size of the array is small enough to be solved directly.

• Application of Expansion Method

  • Use the expansion method to analyze the time complexity of the divide and conquer algorithm. Firstly, expand the recursive relations, then construct the recursion tree, and finally solve the recursion tree to obtain the time complexity of the algorithm.

• Analysis of Time Complexity

  • Time Complexity of Divide Step: Typically Θ(1).
  • Time Complexity of Combine Step: Typically Θ(n).
  • Time Complexity of Recursive Calls: O(logn).
  • Combining the above steps, the time complexity of the maximum subarray problem is O(nlogn).

• Efficiency Analysis of the Algorithm

  • The divide and conquer algorithm for the maximum subarray problem is efficient when handling large-scale arrays because it decomposes the problem into smaller subproblems, solves them recursively, and then merges the solutions.
  • The algorithm’s time complexity is O(nlogn), suitable for handling large-scale arrays.

Master theorem (Custom Method)

The Master Theorem is a method used to solve recursive relations, particularly applicable to recursive relations in divide and conquer algorithms. It provides a quick way to calculate the time complexity of recursive algorithms without the need for detailed expansion and solving of recursive relations.

The Master Theorem is applicable to recursive relations of the following form:

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

Here, ‘a’ is the number of recursive steps, ‘n/b’ is the size of each recursive step, and ‘f(n)’ represents the workload other than the recursive steps.

The basic idea of the Master Theorem is to determine the time complexity of the recursive algorithm by comparing the number of recursive steps ‘a’, the ratio of sizes ‘n/b’, and the growth rate of the workload ‘f(n)’.

The Master Theorem has three cases:

1. If f(n) = O(n^c), where c < log_b(a), then the time complexity of the recursive algorithm is T(n) = Θ(n^log_b(a)).
2. If f(n) = Θ(n^c log^k n), where k ≥ 0 and c = log_b(a), then the time complexity of the recursive algorithm is T(n) = Θ(n^c log^(k+1) n).
3. If f(n) = Ω(n^c), where c > log_b(a), and af(n/b) ≤ kf(n) (for some constant k < 1 and sufficiently large n), then the time complexity of the recursive algorithm is T(n) = Θ(f(n)).

It’s important to note that the Master Theorem is only applicable to specific forms of recursive relations, and may not provide accurate time complexity for other forms of recursive relations.

Discussion and Conclusion

In this lesson, the instructor introduced

• how to solve recursive relations, focusing on divide-and-conquer algorithm.
• Demonstrated relationship between divide-and-conquer algorithm and recursive relations through examples.
• Explained setting up recursive relations.
• Introduced standard method for solving recursive relations, known as expansion method.
• Showed solving recursive relations by expanding them multiple times.
• Provided solutions for merge sort and maximum subarray problem.
• Mentioned solution method for recursive relations in general context, called master theorem.
• Master theorem offers solutions to recursive relations based on different scenarios.

Reference

¹ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. “Introduction to Algorithms,” Third Edition. The MIT Press, 2009. ↩
² Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser. “Data Structures and Algorithms in Python,” Wiley, 2013. ↩
³ Sedgewick, Robert, Wayne, Kevin. “Algorithms,” Fourth Edition. Addison-Wesley Professional, 2011. ↩
⁴ Dasgupta, Papadimitriou, Vazirani. “Algorithms,” McGraw-Hill Science/Engineering/Math, 2008. ↩