Divide and Conquer Recurrences

Discrete Math · Axiom Academy

LESSON Master Theorem for Divide and Conquer A powerful tool for analyzing the time complexity of recursive algorithms using the recurrence relation T(n) = aT(n/b) + f(n). Divide-and-conquer algorithms typically follow this pattern: a: Number of subproblems (a ≥ 1) n/b: Size of each subproblem (b > 1) f(n): Cost of dividing and combining To understand where the Master Theorem comes from, we visualize the recursion as a tree. Each level represents a stage of recursion, and we sum the work at each level. Work per node at level i: f(n/b i ) The Master Theorem compares f(n) with n log b a to determine which part dominates the total cost. Let's apply the Master Theorem to analyze some famous algorithms: a = 2, b = 2, f(n) = Θ(n) n log 2 2 = n = Θ(n) Case 2: T(n) = Θ(n log n) a = 1, b = 2, f(n) = Θ(1) n log 2 1 = n 0 = 1 Case 2: T(n) = Θ(log n) a = 3, b = 2, f(n) = Θ(n) n log 2 3 ≈ n 1.585 Case 1: T(n) = Θ(n 1.585 ) a = 7, b = 2, f(n) = Θ(n 2 ) n log 2 7 ≈ n 2.807 Case 1: T(n) = Θ(n 2.807 )

This is the written version of the interactive lesson above. See the full Discrete Math course.