{"title":"Master Theorem","description":null,"content":"When you study recursive algorithms like **Merge Sort**, **Binary Search**, or **Quick Sort**, you’ll often end up writing a recurrence relation like:\n\n`T(n) = 2T(n/2) + n`\n\nAt this point, most beginners get stuck: “How do I find the time complexity from this?”\n\nYou could expand it manually… or use recursion trees…\n\nBut there’s a **faster way**.\n\nThat’s where the **Master Theorem** comes in — a direct formula to solve most **divide-and-conquer recurrences** in seconds.\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 the problem is divided into\n- `n/b`: Size of each subproblem\n- `f(n)`: Cost of dividing, merging, or combining the results\n\nIt helps us find the **asymptotic time complexity (Big O)** directly without manually expanding the recurrence.\n\n\n> **TIP**\n>\n> #### The Intuition Behind It\n>\n> Imagine you have a big problem of size `n`.\n>\n> Each recursive call breaks it into `a` subproblems of size `n/b`. You also spend some extra effort `f(n)` outside recursion (like merging or partitioning).\n>\n> The total time is the **sum of all work done across recursion levels**.\n>\n> So the total cost = **Work in subproblems** + **Work outside recursion**.\n>\n> The Master Theorem compares **which part dominates** — the recursive work or the combining work.\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\nDefine the **benchmark work** from the recursion tree (ignoring *f*):\n\n\n$$n^{\\log_b a}$$\n\n\nNow compare `f(n)` with:\n\n\n$$n^{\\log_b a}$$\n\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\nThis means, the non-recursive work `f(n)` grows strictly **slower** than the work contributed by the subproblems.\n\n**Result:**\n\n\n$$T(n) = \\Theta\\left(n^{\\log_b a}\\right)$$\n\n\n**Intuition:** Most of the time is spent **inside recursion**; the combine work is negligible by comparison.\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\nThat means **both recursive and combining work grow equally fast**.\n\n**Result:**\n\n\n$$T(n) = \\Theta\\left(n^{\\log_b a} \\log n\\right)$$\n\n\n**Intuition:** Each level of recursion does the same amount of work → multiply by log n levels.\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 if **a × f(n/b) ≤ c × f(n)** for some constant `c < 1` and sufficiently large n (called the **regularity condition**),\n\nthen:\n\n\n$$T(n) = \\Theta(f(n))$$\n\n\n**Intuition:** The **combine step** `f(n)` is doing so much work that the recursive calls become insignificant.\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\nCompute:\n\n\n$$n^{\\log_b a} = n^{\\log_2 1} = n^0 = 1$$\n\n\n→ f(n) = Θ(n⁰) → 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\nCompute:\n\n\n$$n^{\\log_b a} = n^{\\log_2 2} = n^1 = n$$\n\n\n→ f(n) = Θ(n¹) → 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\nNot in Master Theorem form because subproblem size is `(n−1)` not `(n/b)`.\n\n❌ **Master Theorem not applicable**\n\nWe’d need **expansion** or **recursion tree** methods.\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: Weird Recurrence**\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 → smaller power → Case 1: **T(n) = Θ(n²)**\n\n---\n\n# When Master Theorem Fails\n\nThe master theorem is powerful but not universal.\n\nYou cannot use it when:\n\n- **Uneven subproblem sizes**: T(n) = T(n/2) + T(n/3) + n\n- **Additive constants instead of fractions**: T(n) = T(n−1) + n\n- **f(n) not positive / irregular**: T(n) = 2T(n/2) − n\n- **Non-polynomial f(n)**: T(n) = 2T(n/2) + log n\n\nIn such cases, use **recursion tree** or **substitution method**.","pageType":"dsa"}

Master Theorem

Ashish Pratap Singh

Get Premium