Course contentsShow
← Computer Science
Lesson 842 of 2,87220. Recursion Patterns and TechniquesFree lesson

Recurrence Relations for Divide and Conquer

Writing recurrence relations to express runtime: T(n) = aT(n/b) + f(n) for analyzing algorithms.

Recurrence Relations for Divide and Conquer

You'll learn how to mathematically express the runtime of divide-and-conquer algorithms using recurrence relations.

When you analyze algorithms like Mergesort or Quicksort, you can't just count operations linearly—these algorithms break problems into smaller pieces recursively. To capture their runtime mathematically, we use recurrence relations.

The Master Template

The standard form for divide-and-conquer recurrences is:

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

Let's decode each piece:

  • T(n) = time to solve a problem of size n
  • a = number of subproblems created
  • n/b = size of each subproblem (problem divided by b)
  • f(n) = work done outside recursion (dividing + combining)

Real Examples You've Seen

Mergesort:

T(n) = 2T(n/2) + O(n)
  • Splits into 2 halves (a=2)
  • Each half has size n/2 (b=2)
  • Merging takes O(n) work (f(n)=n)

Binary Search:

T(n) = 1T(n/2) + O(1)
  • Searches only 1 half (a=1)
  • Half the size (b=2)
  • Comparison work is constant (f(n)=1)

Why This Matters

Think of it like a recipe that calls for itself: "To bake a cake for n people, bake two half-sized cakes and spend n minutes frosting them together." The recurrence relation captures exactly this self-referential structure, letting us calculate total time mathematically instead of guessing.

Once you write the recurrence, you can solve it (using techniques you'll learn next) to find the algorithm's Big-O complexity.

Key Takeaway: Recurrence relations express divide-and-conquer runtime as T(n) = aT(n/b) + f(n), where a subproblems of size n/b are solved plus f(n) work for splitting and combining.