Course contentsShow
← Mathematics
Lesson 2636 of 3,12152. CombinatoricsFree lesson

Divide-and-Conquer Recurrences

Analyze recurrences arising from divide-and-conquer algorithms using the Master Theorem for asymptotic behavior.

Divide-and-Conquer Recurrences

You'll learn how to analyze the runtime of algorithms that split problems into smaller pieces using the Master Theorem.

The Core Idea

Many efficient algorithms—like merge sort or binary search—work by dividing a problem of size n into a smaller subproblems, each of size n/b, then combining the results. This strategy produces recurrence relations of the form:

T(n) = a·T(n/b) + f(n)

where f(n) represents the cost of dividing and combining.

Instead of solving these recurrences by hand each time, the Master Theorem gives us a shortcut to determine asymptotic behavior by comparing the "splitting work" (controlled by a and b) with the "combining work" (f(n)).

The Master Theorem (Simplified Form)

For T(n) = a·T(n/b) + f(n) where a ≥ 1, b > 1:

  1. Case 1: If f(n) grows slower than n^(log_b a), then T(n) = Θ(n^(log_b a))
    (The recursive splitting dominates)

  2. Case 2: If f(n) grows at exactly the same rate as n^(log_b a), then T(n) = Θ(n^(log_b a) · log n)
    (Both parts contribute equally)

  3. Case 3: If f(n) grows faster than n^(log_b a), then T(n) = Θ(f(n))
    (The combining work dominates)

Example

Merge sort: T(n) = 2·T(n/2) + n

  • Here a = 2, b = 2, f(n) = n
  • n^(log₂ 2) = n¹ = n
  • Since f(n) = n matches this rate → Case 2 → T(n) = Θ(n log n)

Key Takeaway: The Master Theorem quickly reveals the asymptotic complexity of divide-and-conquer recurrences by comparing recursive splitting costs with combining costs.