Recurrence Relations

When you stare at merge sort or binary search, the running time is not naturally a simple sum like `n^2/2 + n/2`. It is something more interesting: the cost of a problem of size `n` is built out of the cost of smaller problems plus a little glue. That self-referential structure is captured by a **recurrence relation**, an equation of the form `T(n) = ...` written in terms of `T` on smaller inputs. This lesson teaches you to spot, write, and classify recurrences directly from recursive code. You will identify the two ingredients every recurrence needs (the recursive case and the base case), then translate familiar algorithms into their `T(n)` equations: factorial gives `T(n) = T(n-1) + 1`, binary search gives `T(n) = T(n/2) + 1`, merge sort gives `T(n) = 2 T(n/2) + n`, and naive Fibonacci gives `T(n) = T(n-1) + T(n-2) + 1`. You will also group recurrences into three families (linear, divide-and-conquer, and multi-branch) and recognize the Big-O class each typically produces. This lesson builds on **Big-O Notation (Upper Bound)**, which gave you the language for expressing complexity, and on **Mathematical Sequences**, which gave you experience with arithmetic, geometric, and Fibonacci-style sequences, exactly the patterns you will see when a recurrence is expanded. Writing a recurrence is half the battle; the other half is converting it into a closed-form Big-O. That is the subject of the very next lesson, **Solving Recurrence Relations**.

Writing the recurrence `T(n) = 2 T(n/2) + n` for merge sort is the easy part. Turning it into the closed-form `O(n log n)` is where the real algorithm analysis happens, and it is exactly what this lesson is for. **Solving Recurrence Relations** gives you a small toolkit that, used well, can analyze nearly every recursive algorithm you will meet in interviews, papers, or production. This lesson walks through five methods. The **Substitution Method** has you guess the solution and prove it by induction, useful when you already suspect the bound. The **Recursion Tree Method** visualizes work level by level and sums it; this is how you see why merge sort spends `n` work per level over `log_2(n)` levels. The **Master Theorem** mechanically solves the divide-and-conquer form `T(n) = a T(n/b) + f(n)` via three cases, and you will memorize when each case fires. The **Extended Master Theorem** patches the gap when `f(n)` includes logarithmic factors. The **Akra-Bazzi Method** generalizes to unequal subproblem sizes that the basic theorem cannot handle. You will practice picking the right tool for each recurrence rather than blindly reaching for the same one every time. This lesson directly continues **Recurrence Relations**, where you learned to write `T(n)` from recursive code, and reuses ideas from **Big-O Notation (Upper Bound)** and **Mathematical Sequences** for the underlying summation arguments. With the analysis sub-track complete, you will pivot back to advanced math in **Modular Arithmetic**, where number-theoretic tools meet algorithm design.