Solving Recurrence Relations

Math for CS · Axiom Academy

Substitution, recursion trees, and the Master theorem Divide-and-conquer algorithms produce recurrences of the form T(n) = aT(n/b) + f(n) . We have three main approaches to find closed-form solutions: Substitution method — guess the answer, then prove it by induction Recursion tree method — draw the tree of recursive calls and sum the work at each level Master theorem — a formula that covers most divide-and-conquer recurrences instantly Each method has strengths. Substitution works for any recurrence if you can guess correctly. Recursion trees build intuition. The Master theorem gives instant answers for standard forms. This is a two-step process: guess the form of the solution, then prove it correct by strong induction. Guess: for some constant c > 0 . Inductive step: Assume for all k < n . Then: The last inequality holds when . So . Draw the full tree of recursive calls. At each level, compute the total work. Then sum across all levels. There are levels, each contributing exactly n work: Consider T(n) = T(n/3) + T(2n/3) + n . The left subtree has depth and the right subtree has depth . Every full level still sums to n , so . Geometric Series in Recursion Trees When the work per level changes geometrically, we get three patterns depending on the common ratio r = a/b^c : For , the work at level i is . r Root dominates. Total = (n^c) . r = 1 (flat): All levels equal. Total . r > 1 (increasing): Leaves dominate. Total . This is exactly the intuition behind the Master theorem!

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