Master Theorem
Table of Contents
1. Overview
- Definition: The Master Theorem provides a method for analyzing the time complexity of recursive algorithms.
- Form: The theorem applies to recurrences of the form T(n) = aT(n/b) + f(n), where:
- T(n) is the time complexity,
- a ≥ 1 is the number of subproblems,
- b > 1 is the factor by which the problem size is reduced,
- f(n) is a function that describes the cost of dividing the problem and combining the results.
- Applications: Often used in the analysis of divide-and-conquer algorithms, such as mergesort and quicksort.
Cases of the Master Theorem:
- Case 1: If f(n) is polynomially smaller than n(logb(a)), then T(n) = Θ(n(logb(a))).
- Case 2: If f(n) is asymptotically the same as n(logb(a)), then T(n) = Θ(n(logb(a)) log(n)).
- Case 3: If f(n) is polynomially larger than n(logb(a)), and the regularity condition holds, then T(n) = Θ(f(n)).