Master Theorem
IT 위키
Master Theorem is a formula used to analyze the time complexity of recursive algorithms, particularly divide-and-conquer algorithms. It provides a direct way to determine asymptotic complexity without requiring iterative expansion or recurrence tree analysis.
Master Theorem Formula[편집 | 원본 편집]
A recurrence of the form:
- T(n) = aT(n/b) + O(n^d)
where:
- a = number of recursive calls,
- b = factor by which the problem size is reduced in each recursion,
- O(n^d) = cost of work done outside the recursive calls,
can be solved using the Master Theorem by comparing d with log_b(a):
Case | Condition | Complexity |
---|---|---|
Case 1 | d > log_b(a) | O(n^d) |
Case 2 | d = log_b(a) | O(n^d log n) |
Case 3 | d < log_b(a) | O(n^(log_b(a))) |
Examples[편집 | 원본 편집]
- Merge Sort
- Recurrence: T(n) = 2T(n/2) + O(n)
- a = 2, b = 2, d = 1
- log_2(2) = 1 → d = log_b(a)
- Case 2 applies → Complexity: O(n log n)
- Binary Search
- Recurrence: T(n) = T(n/2) + O(1)
- a = 1, b = 2, d = 0
- log_2(1) = 0 → d = log_b(a)
- Case 2 applies → Complexity: O(log n)
- Strassen’s Matrix Multiplication
- Recurrence: T(n) = 7T(n/2) + O(n²)
- a = 7, b = 2, d = 2
- log_2(7) ≈ 2.81 → d < log_b(a)
- Case 3 applies → Complexity: O(n^2.81)
Limitations[편집 | 원본 편집]
- Only applicable for recurrences that match the form T(n) = aT(n/b) + O(n^d).
- Does not work well for irregular or non-uniform recurrence relations.
Applications[편집 | 원본 편집]
- Divide-and-Conquer Algorithms: Merge Sort, Quick Sort, Binary Search.
- Matrix Multiplication: Strassen’s Algorithm.
- Computational Complexity Analysis: Used in algorithm design and performance evaluation.