Master Theorem

## The form the theorem expects The master theorem solves recurrences shaped like ``` T(n) = a·T(n/b) + f(n) ``` where **a ≥ 1** is the number of subproblems each call spawns, **b > 1** is the factor the input size is *divided* by for each subproblem, and **f(n)** is all the non-recursive work a single call does — the splitting before the calls plus the combining after them. Both a and b must be constants; f(n) must be asymptotically positive. Reading a recurrence off a routine is a two-question exercise: *how many times does it call itself*, and *how big is each of those calls' inputs relative to n*. For a routine that inspects one position, decides, and then recurses on half of what is left, the answers are "once" and "n/2", giving a = 1 and b = 2. The remaining work — computing the midpoint, one comparison — does not grow with n, so f(n) = Θ(1). ## The comparison the theorem makes Everything hinges on one quantity, often called the watershed: ``` n^(log_b a) ``` This is the total cost of all the leaves of the recursion — the number of base-case calls. The theorem compares it against f(n), the cost at the top: | relation | case | result | |---|---|---| | f(n) polynomially smaller than n^(log_b a) | 1 | Θ(n^(log_b a)) — leaves dominate | | f(n) = Θ(n^(log_b a)) | 2 | Θ(n^(log_b a) · log n) — every level costs the same | | f(n) polynomially larger (plus a regularity condition) | 3 | Θ(f(n)) — the root dominates | For a = 1 and b = 2: log_2 1 = 0, so the watershed is n^0 = 1. And f(n) = Θ(1) = Θ(n^0). The two sides are equal, so this is **case 2**, and the result is Θ(n^0 · log n) = **Θ(log n)**. ## Why the answer is not Θ(n) The most common wrong answer is "you are halving n, and half of n is still proportional to n, so it is linear." That confuses *the size of the remaining input* with *the work performed*. Nothing here touches n/2 items; the call hands off a smaller region and does constant work itself. Sum the work down the chain: 1 + 1 + 1 + … once per level, and the levels stop when n/2^k reaches the base case, i.e. after about log₂ n levels. The sum is Θ(log n). The mirror-image wrong answer is "each call is O(1), so the whole thing is O(1)." f(n) is the cost of **one** call, never of the recursion. The recurrence exists precisely because you must add up all the calls. ## What a single parameter change does The same shape with a different a is a completely different function, which is why the theorem is worth internalising rather than memorising results: | recurrence | watershed | case | result | |---|---|---|---| | T(n) = T(n/2) + Θ(1) | n^0 = 1 | 2 | Θ(log n) | | T(n) = 2T(n/2) + Θ(1) | n^1 = n | 1 | Θ(n) | | T(n) = 2T(n/3) + Θ(1) | n^(log_3 2) ≈ n^0.63 | 1 | Θ(n^0.63) | Going from one recursive call to two turns a logarithm into a linear count, because the recursion tree now has about n leaves instead of one call per level. Going from halves to thirds while keeping two calls lands between the two. Nothing about f(n) changed in any of these rows — the exponent in a leaf-dominated recurrence is fixed by a and b alone. ## Details worth being precise about - **Floors and ceilings do not matter.** Real inputs give ⌊n/2⌋ or ⌈n/2⌉; the master theorem is stated so that the asymptotic answer is unaffected. Do not spend interview time on them. - **The base of the logarithm does not matter asymptotically.** log₂ n and log₁₀ n differ by a constant factor, so Θ(log n) needs no base. The base *does* set the constant, which is why dividing by 3 instead of 2 is a real but constant-factor win. - **Recursion depth is space.** A chain of Θ(log n) calls costs Θ(log n) stack frames unless the call is the last thing the routine does and the compiler eliminates it. The time answer does not report that; you must. - **Θ versus O.** If the per-call work is stated as O(1) rather than Θ(1) — an upper bound only — the honest conclusion is O(log n). Interviewers rarely press on this, but stating the bound you actually derived is a mark of care.