{"title":"Recurrence Relations","description":null,"content":"When you analyze a recursive algorithm, the running time isn't obvious by looking at it. A function that calls itself doesn't have a simple loop count you can read off the page.\n\nBut there is a pattern to lean on: the cost of solving a problem of size `n` is written in terms of the cost of the smaller subproblems it calls. That self-referential definition is exactly what a **recurrence relation** captures.\n\n---\n\n# **What Is a Recurrence Relation?**\n\nA **recurrence relation** expresses a sequence or function in terms of its own earlier values.\n\nPut plainly:\n\n> A recurrence relation tells you how to compute the next value from the ones that came before it.\n\nThe classic Fibonacci sequence is a clean example:\n\n\n```shell\n0, 1, 1, 2, 3, 5, 8, 13, ...\n```\n\n\nEach number is the sum of the two before it.\n\nThat rule can be expressed mathematically as: `F(n) = F(n−1) + F(n−2)`\n\nwith base cases: `F(0) = 0, F(1) = 1`\n\nThat formula is a recurrence relation. It defines each term using the terms before it, and that is the same idea we use to analyze the running time of recursive algorithms.\n\n---\n\n# Why Do We Need Recurrence Relations?\n\nWhen you write a recursive function, each call does some work of its own and then hands the rest off to calls on smaller inputs. That structure translates directly into a recurrence relation.\n\nTake merge sort, for instance:\n\n\n```shell\nT(n) = 2T(n/2) + O(n)\n```\n\n\nReading it piece by piece:\n\n- The array is split into 2 halves that are each sorted recursively → `2T(n/2)`\n- Merging the two sorted halves back together takes linear time → `O(n)`\n\nThis recurrence captures how the total time `T(n)` depends on the cost of its subproblems. Solving it gives the familiar `O(n log n)`.\n\nA recurrence relation, then, is just recursion written as a cost equation.\n\n---\n\n# The General Form\n\nA recurrence relation generally looks like this:\n\n\n```shell\nT(n) = a×T(n/b) + f(n)\n```\n\n\nWhere:\n\n- `a` = number of subproblems each call spawns\n- `b` = factor by which the input shrinks, so each subproblem has size `n/b`\n- `f(n)` = work done outside the recursive calls (like merging or partitioning)\n\nA few common algorithms and their recurrences:\n\n\n| **Algorithm** | Recurrence | Explanation |\n| --- | --- | --- |\n| **Binary Search** | T(n) = T(n/2) + O(1) | Recurse into one half, constant work per call |\n| **Merge Sort** | T(n) = 2T(n/2) + O(n) | Split into 2 halves, recurse on both, then merge |\n| **Quick Sort (best)** | T(n) = 2T(n/2) + O(n) | A balanced partition splits the array in half |\n| **Tower of Hanoi** | T(n) = 2T(n−1) + O(1) | Two recursive moves of a stack one smaller |\n\n\nThe quick sort row needs a caveat. `T(n) = 2T(n/2) + O(n)` is quick sort's *best case*, where every partition splits the array evenly. Its average case is also O(n log n), but the recurrence is different: the pivot lands at a random position, so the analysis averages the cost over all possible split points rather than assuming a clean halving. And when partitions are maximally unbalanced, quick sort degrades to T(n) = T(n−1) + O(n), which is O(n²).\n\n---\n\n# Visualizing Recurrence Relations\n\nA recursion tree is the clearest way to see where the time goes. Let’s draw one for merge sort’s recurrence `T(n) = 2T(n/2) + n`. Each node is a call, and it branches into the two half-size calls it makes:\n\n\n```mermaid\ngraph TD\n A[\"T(n)\"]:::lvl0 --> B[\"T(n/2)\"]:::lvl1\n A --> C[\"T(n/2)\"]:::lvl1\n B --> D[\"T(n/4)\"]:::lvl2\n B --> E[\"T(n/4)\"]:::lvl2\n C --> F[\"T(n/4)\"]:::lvl2\n C --> G[\"T(n/4)\"]:::lvl2\n D --> H[\"...\"]:::dots\n E --> H\n F --> H\n G --> H\n\n classDef lvl0 fill:#00ceff,stroke:#000,color:#000\n classDef lvl1 fill:#ffa94d,stroke:#000,color:#000\n classDef lvl2 fill:#38d9a9,stroke:#000,color:#000\n classDef dots fill:#ffd43b,stroke:#000,color:#000\n```\n\n\nThe key observation is that the work *at each level* of the tree adds up to `n`. The top level does `n` work in one call. The next level has two calls doing `n/2` each, which is `n` again. The level below has four calls doing `n/4` each, still `n`. Halving the size while doubling the number of calls keeps the per-level total constant.\n\nSince each call halves the input, the tree is `log n` levels deep. Multiply the per-level work by the number of levels and you get `n × log n`, which is the O(n log n) we expected.\n\n---\n\n# How to Solve Recurrence Relations\n\nWriting a recurrence is only half the job. Solving it is what turns `T(n) = 2T(n/2) + n` into a Big O you can actually compare against other algorithms.\n\nThere are four techniques worth knowing, roughly in order of how often they come up:\n\n1. **Substitution method** (guess and check)\n2. **Recursion tree method**\n3. **Iterative expansion**\n4. **Master theorem**\n\nWe'll work through the first three here, and the master theorem gets its own chapter next.\n\n## **(a) Substitution Method**\n\nThis is the most direct method. You guess the answer, based on a similar recurrence or the shape of the problem, then prove the guess is correct using mathematical induction.\n\nGiven the recurrence: `T(n) = 2T(n/2) + n`\n\n#### **Step 1. Guess the solution**\n\nWe suspect `T(n) = O(n log n)`, because we halve the problem and recurse on both halves, then do linear work to merge.\n\n#### **Step 2. Prove it by induction**\n\nWe want to show that `T(n) ≤ c·n·log n` for some constant `c` and all `n` past a starting point.\n\n**Base case:**\n\nWe anchor the induction at `n = 2` rather than `n = 1`. At `n = 1` the bound `c·n·log n` collapses to `c·1·log 1 = 0`, but `T(1)` is a positive constant, so the bound can't hold there. At `n = 2`, `T(2)` is a constant and `c·2·log 2 = 2c`, so we can pick `c` large enough that `T(2) ≤ 2c` holds.\n\n**Inductive step:**\n\nAssume the bound holds for all smaller sizes, in particular for `n/2`. Starting from the recurrence:\n\nT(n) = 2T(n/2) + n\n\nSubstitute the inductive hypothesis:\n\n\n$$T(n) \\le 2c \\cdot \\frac{n}{2} \\log\\frac{n}{2} + n \\\\[4pt]\nT(n) \\le c n (\\log n - 1) + n \\\\[4pt]\nT(n) \\le c n \\log n - c n + n \\\\[4pt]\nT(n) \\le c n \\log n - n (c - 1)$$\n\n\nFor any `c > 1`, the term `n(c − 1)` is positive, so `T(n) ≤ c·n·log n − n(c − 1) ≤ c·n·log n`. The bound holds, which confirms `T(n) = O(n log n)`.\n\n## **(b) Recursion Tree Method**\n\nInstead of guessing, the recursion tree method unfolds the recurrence into a tree and adds up the work done at each level. It's the method behind the visualization we drew earlier, made systematic.\n\nTake merge sort again: `T(n) = 2T(n/2) + n`. Laying out the work level by level:\n\n\n| Level | Number of calls | Work per call | Work this level |\n| --- | --- | --- | --- |\n| 0 | 1 | n | n |\n| 1 | 2 | n/2 | n |\n| 2 | 4 | n/4 | n |\n| ... | ... | ... | ... |\n| log n | n | 1 | n |\n\n\nEvery level sums to `n`, and the tree is `log n` levels deep because the input keeps halving until it reaches size 1. The total is the per-level work times the number of levels:\n\n\n```shell\nT(n) = n + n + n + ... + n = n × log n → O(n log n)\n```\n\n\nThis method is especially useful when `f(n)` isn't constant across levels, because you can see exactly how the work is distributed instead of having to guess a closed form.\n\n## **(c) Iterative Expansion**\n\nWhen a recurrence shrinks by subtraction rather than division (so the recursion tree degenerates into a single chain), the cleanest approach is to expand it by hand until a pattern appears, then sum the series.\n\nTake `T(n) = T(n−1) + n`:\n\n\n```shell\nT(n) = T(n-1) + n\n = T(n-2) + (n-1) + n\n = T(n-3) + (n-2) + (n-1) + n\n = ...\n = T(1) + (2 + 3 + ... + n)\n```\n\n\nThe leftover terms form an arithmetic series. Since `1 + 2 + 3 + ... + n = n(n+1)/2`, the whole sum grows like `n²/2`, which is O(n²). This is exactly the recurrence for an unbalanced quick sort, which is why its worst case is quadratic.\n\n## **(d) Master Theorem**\n\nFor the common divide-and-conquer shape `T(n) = aT(n/b) + f(n)`, you don't need substitution, a recursion tree, or manual expansion at all. The **Master Theorem** reads the answer straight off the values of `a`, `b`, and `f(n)`.\n\nIt's the fastest way to solve most divide-and-conquer recurrences, and it's important enough to get its own chapter.\n\n---\n\nSubstitution, recursion trees, and iterative expansion will carry you through almost any recurrence you need to analyze by hand. But for that one extremely common shape, `T(n) = aT(n/b) + f(n)`, there's a direct formula that skips the work entirely.\n\nThat formula is the **Master Theorem**, which we'll cover in the next chapter.\n\n---\n\n# Quiz","pageType":"dsa"}

Recurrence Relations

Get Premium