{"title":"Master Theorem","description":null,"content":"Divide-and-conquer algorithms like merge sort, binary search, and quick sort all lead to a recurrence of the same shape:\n\n`T(n) = 2T(n/2) + n`\n\nYou could solve it by expanding it by hand or drawing a recursion tree, but for this family of recurrences there's a much faster path.\n\nThe **Master Theorem** is a formula that reads the Big O of most divide-and-conquer recurrences straight off their structure, with no expansion or induction.\n\n---\n\n# **What is Master Theorem?**\n\nThe Master Theorem applies to recurrences of the form:\n\n`T(n) = aT(n/b) + f(n)`\n\nWhere:\n\n- `a`: number of subproblems each call splits into\n- `b`: factor the input shrinks by, so each subproblem has size `n/b`\n- `f(n)`: cost of the work done outside the recursive calls (dividing, merging, or combining)\n\nThe whole point is to find the asymptotic complexity directly, without expanding the recurrence by hand.\n\n\n> **TIP**\n>\n> #### The Intuition Behind It\n>\n> Consider a problem of size `n`.\n>\n> Each recursive call breaks it into `a` subproblems of size `n/b`, and spends some extra effort `f(n)` outside recursion (like merging or partitioning).\n>\n> The total time is the sum of all the work done across every level of recursion, which splits into two parts: the work inside the subproblems, and the work outside recursion.\n>\n> The Master Theorem simply compares which of those two parts dominates: the recursive work or the combining work. Whichever wins decides the answer.\n\n\n---\n\n# The Three Cases\n\nWe analyze recurrences of the form:\n\n\n$$T(n) = aT\\left(\\frac{n}{b}\\right) + f(n)$$\n\n\nEverything hinges on one quantity, the watershed:\n\n\n$$n^{\\log_b a}$$\n\n\nThis is the total work done at the bottom of the recursion tree. A tree that branches `a` ways and is `log_b n` levels deep has `a^(log_b n)` leaves, which equals `n^(log_b a)`, and each leaf does constant work. So `n^(log_b a)` measures the recursive side of the cost, and the three cases all come down to comparing the combine work `f(n)` against it: is `f(n)` smaller, equal, or larger?\n\n### **Case 1: Subproblem Work Dominates**\n\nCondition:\n\n\n$$f(n) = O\\left(n^{\\log_b a - \\varepsilon}\\right) \\quad \\text{for some } \\varepsilon > 0$$\n\n\nIn words, the combine work `f(n)` grows polynomially slower than the recursive work `n^(log_b a)`. The `ε > 0` is what makes \"slower\" mean slower by a factor of some power of `n`, not just by a constant or a log.\n\n**Result:**\n\n\n$$T(n) = \\Theta\\left(n^{\\log_b a}\\right)$$\n\n\n**Intuition:** almost all the time is spent inside the recursion. The combine work is negligible by comparison, so the leaf work `n^(log_b a)` sets the complexity.\n\n**Example:**\n\n\n$$T(n) = 8T\\left(\\frac{n}{2}\\right) + O(n^2)$$\n\n\nHere: a = 8, b = 2 → log₂8 = 3\n\n\n$$f(n) = n^2 = O\\left(n^{3 - 1}\\right) \\Rightarrow \\text{smaller power} \\; \\Rightarrow \\; T(n) = \\Theta(n^3)$$\n\n\n### **Case 2: Both Parts Balance**\n\n**Condition**\n\n\n$$f(n) = \\Theta\\left(n^{\\log_b a}\\right)$$\n\n\nThe recursive work and the combine work grow at the same rate.\n\n**Result:**\n\n\n$$T(n) = \\Theta\\left(n^{\\log_b a} \\log n\\right)$$\n\n\n**Intuition:** every level of the recursion tree does roughly the same amount of work, and there are `log n` levels, so the total is that per-level work times `log n`.\n\n**Example:**\n\n\n$$T(n) = 2T\\left(\\frac{n}{2}\\right) + n$$\n\n\nHere:\n\n- a = 2, b = 2 → log₂2 = 1\n- f(n) = n = Θ(n¹) → same order: **T(n) = Θ(n log n)**\n\n### **Case 3: Outside Work Dominates**\n\nIf\n\n\n$$f(n) = \\Omega\\left(n^{\\log_b a + \\varepsilon}\\right)$$\n\n\nand the regularity condition `a × f(n/b) ≤ c × f(n)` holds for some constant `c < 1` and all sufficiently large `n`,\n\nthen:\n\n\n$$T(n) = \\Theta(f(n))$$\n\n\n**Intuition:** the combine step `f(n)` does so much work that the recursive calls become insignificant, so `f(n)` sets the complexity. The regularity condition rules out oddly behaved `f(n)` and guarantees the top-level cost keeps dominating all the way down.\n\n**Example:**\n\n\n$$T(n) = 2T\\left(\\frac{n}{2}\\right) + n^2$$\n\n\nHere:\n\n- a = 2, b = 2 → log₂2 = 1\n\n\n$$f(n) = n^2 = \\Omega\\left(n^{1 + \\varepsilon}\\right) \\Rightarrow \\text{faster than recursion} \\; \\Rightarrow \\; T(n) = \\Theta(n^2)$$\n\n\n---\n\n# **Step-by-Step Examples**\n\n### **Example 1: Binary Search**\n\n\n$$T(n) = T\\left(\\frac{n}{2}\\right) + 1$$\n\n\n- a = 1, b = 2, f(n) = 1\n\nThe watershed is:\n\n\n$$n^{\\log_b a} = n^{\\log_2 1} = n^0 = 1$$\n\n\nSo f(n) = Θ(1) = Θ(n⁰), which matches the watershed → Case 2: **T(n) = Θ(log n)**\n\n### **Example 2: Merge Sort**\n\n\n$$T(n) = 2T\\left(\\frac{n}{2}\\right) + n$$\n\n\n- a = 2, b = 2, f(n) = n\n\nThe watershed is:\n\n\n$$n^{\\log_b a} = n^{\\log_2 2} = n^1 = n$$\n\n\nSo f(n) = Θ(n¹), which matches the watershed → Case 2: **T(n) = Θ(n log n)**\n\n### **Example 3: Tower of Hanoi**\n\n\n$$T(n) = 2T(n - 1) + 1$$\n\n\nThis isn't in Master Theorem form: the subproblem size is `n−1`, not `n/b`. The input shrinks by subtraction, not division, so there's no `b` to work with and the theorem doesn't apply.\n\nExpanding it by hand instead gives T(n) = 1 + 2 + 4 + ... + 2^(n−1), which is Θ(2ⁿ).\n\n### **Example 4: Strassen’s Matrix Multiplication**\n\n\n$$T(n) = 7T\\left(\\frac{n}{2}\\right) + O(n^2)$$\n\n\nHere:\n\n- a = 7, b = 2 → log₂7 ≈ 2.81\n- f(n) = n²\n\n\n$$\\text{Since } f(n) = O\\left(n^{2.81 - \\varepsilon}\\right) \\Rightarrow \\text{Case 1 applies: } T(n) = \\Theta\\left(n^{2.81}\\right)$$\n\n\nThis is how Strassen’s algorithm beats the classic `O(n³)` approach.\n\n### **Example 5: Many Subproblems, Cheap Combine**\n\n\n$$T(n) = 9T\\left(\\frac{n}{3}\\right) + n$$\n\n\n- a = 9, b = 3 → log₃9 = 2\n- f(n) = n, which is a smaller power than n² → Case 1: **T(n) = Θ(n²)**\n\nEven though the combine step is linear, the recursion spawns so many subproblems that the leaf work `n²` swamps it.\n\n---\n\n# When Master Theorem Fails\n\nThe master theorem is widely applicable but not universal. It assumes a specific shape: equal-sized subproblems, a division-based split, and an `f(n)` that is polynomially comparable to the watershed `n^(log_b a)`. It breaks down when any of those assumptions is violated.\n\nYou cannot use it when:\n\n- **Subproblems have different sizes**, like `T(n) = T(n/2) + T(n/3) + n`. The single `a` and `b` no longer describe the recursion. (The Akra-Bazzi method handles these.)\n- **The input shrinks by subtraction, not division**, like `T(n) = T(n−1) + n`. There's no `n/b` to plug in, so you fall back to expansion.\n- **f(n) is negative or not well behaved**, like `T(n) = 2T(n/2) − n`. The theorem assumes a non-negative combine cost.\n- **f(n) sits in the gap**, neither polynomially smaller nor polynomially larger than `n^(log_b a)`, like `T(n) = 2T(n/2) + n log n`. Here the watershed is `n`, and `n log n` beats it by only a log factor, not by a factor of `n^ε`, so none of the three cases apply. (This is different from `T(n) = 2T(n/2) + log n`, which the theorem *does* solve: `log n` is polynomially smaller than `n`, so Case 1 gives Θ(n).)\n\nIn these cases, fall back to the recursion tree or substitution methods from the previous chapter.\n\n---\n\nFor most divide-and-conquer recurrences, the Master Theorem lets you read off the complexity in one step, without drawing a recursion tree or running induction. For the cases where it does not apply, the substitution and recursion-tree methods from the previous chapter fill the gap.\n\nTogether with Big O notation, best/worst/average case analysis, amortized analysis, and recurrence relations, this completes the foundation for reasoning about how any algorithm scales as input grows.\n\n---\n\n# Quiz","pageType":"dsa"}

Get Premium