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.

See Also[편집 | 원본 편집]