Why can't the master theorem solve T(n) = T(n-1) + O(n), and what does?
answer
- Check the form before checking the cases
- Is the shrinkage division or subtraction?
- Solve n/b = n−1 for constant b
- Depth is n here, not log n
- Sum n + (n−1) + ... + 1
basics
~20 sThe master theorem covers only T(n) = a·T(n/b) + f(n), where a subproblem is n divided by a constant b above 1. Subtracting one leaves no such b, so no case applies. Summing the per-call work gives Θ(n^2).
solid answer
~50 sThe theorem's form requires the subproblem size to be `n/b` for a constant b > 1, which makes the recursion about log_b n levels deep. Subtracting a constant instead gives a depth of n, a completely different regime, so no case applies — there is nothing to plug in for b. Solve it by unrolling: the calls do n, n−1, n−2, … , 1 units of work, and that sum is n(n+1)/2 = Θ(n^2). The same out-of-scope verdict applies to unequal splits like `T(n) = T(n/3) + T(2n/3) + O(n)`, where the two subproblems differ in size; that one needs a direct argument or the Akra-Bazzi generalisation, and works out to Θ(n log n). The tools for anything outside the form are unrolling into a sum, substitution with induction to verify a guessed bound, or Akra-Bazzi.
code
pseudocode · 9 linesSTRIP-LARGEST(amounts, n)
if n <= 1
return
m = 0
for i in 1..n-1
if amounts[i] > amounts[m]
m = i
swap(amounts[m], amounts[n-1])
STRIP-LARGEST(amounts, n-1)go deeper
Know that the master theorem needs the input to be divided by a constant, not reduced by one. If a routine peels off a single element per call, expect a depth of n and reach for a sum instead.
Explain why no constant b satisfies n/b = n−1, then unroll to the arithmetic series and state Θ(n^2). Distinguish the subtractive case from the balanced halving case out loud.
Report the Θ(n) stack depth alongside the time bound and say when that turns a slow routine into a crashing one. Recognise unequal splits and log-factor gaps as separate failure modes with separate remedies.
Own the judgment of when a recurrence analysis is worth the effort at all: for a subtractive routine over inputs capped at a few thousand entries, the recursion depth risk usually justifies rewriting it as a loop long before the quadratic term does.
## What the form actually requires ``` T(n) = a·T(n/b) + f(n), a ≥ 1 constant, b > 1 constant, f(n) asymptotically positive ``` Every word carries weight. **a and b must be constants** — a recurrence whose branching depends on n is out. **b must exceed 1** — the size must shrink *multiplicatively*. **All subproblems must be the same size** — the form has one term, not a sum of differently sized terms. Violate any of these and the theorem simply does not apply; it does not "apply approximately". ## Why subtraction breaks it `T(n) = T(n−1) + O(n)` looks obedient: one recursive call, some extra work. But solving `n/b = n − 1` for a constant b is impossible — the implied "b" is n/(n−1), which drifts toward 1 as n grows. The consequence is structural rather than technical: dividing by a constant gives a recursion **log_b n levels deep**, while subtracting a constant gives one **n levels deep**. Those are different worlds, and a theorem built for the first says nothing about the second. ## Solving it directly Unroll the recurrence: ``` T(n) = T(n−1) + c·n = T(n−2) + c·(n−1) + c·n = ... = c·(1 + 2 + ... + n) = c·n(n+1)/2 = Θ(n^2) ``` The attached fragment is the canonical shape: a linear scan to find the largest amount, a swap to park it at the end, then a recursive call on the first n−1 entries. Each call is linear, there are n calls, and the arithmetic series gives Θ(n^2). The close cousin `T(n) = T(n−1) + O(1)` is Θ(n), not Θ(log n) — a mistake that follows from pattern-matching "one recursive call" to the halving case. One call per level says nothing until you know how fast the size falls. ## Space is part of the answer A linear-shrinking recursion is n frames deep. That is **Θ(n) stack space**, which on large inputs is a crash rather than a slowdown, and it is the practical reason such routines get rewritten as loops. The master theorem reports time only; depth is yours to state. A halving recursion, by contrast, is Θ(log n) deep and effectively free. ## Other shapes that fall outside | recurrence | why it is out | what it actually is | |---|---|---| | T(n) = T(n−1) + Θ(n) | subtractive shrinkage | Θ(n^2) | | T(n) = T(n−1) + Θ(1) | subtractive shrinkage | Θ(n) | | T(n) = T(n/3) + T(2n/3) + Θ(n) | unequal subproblem sizes | Θ(n log n) | | T(n) = 2T(√n) + Θ(log n) | shrinkage is not division by a constant | Θ(log n · log log n) | | T(n) = n·T(n/2) + Θ(n) | a is not a constant | outside every case | | T(n) = 2T(n/2) + n·log n | right form, but the gap is only logarithmic | Θ(n · log²n) | That last row is worth separating from the rest: it *is* of the required form. It fails for a different reason — f(n) exceeds the watershed n by a log factor rather than a polynomial one, so neither case 2 nor case 3 fits. "Wrong shape" and "right shape, no case" are two distinct failure modes, and naming which one you hit is a strong signal in an interview. ## The toolkit when the theorem is out 1. **Unroll into a sum.** Expand a few levels, spot the pattern, sum it. This is what settles every subtractive recurrence in one line. 2. **Substitution.** Guess a bound and prove it by induction, tightening the guess when the constants do not close. Slower, but it works on anything and is how the guessed answers get verified. 3. **Akra-Bazzi.** The generalisation built for unequal splits and messier f; heavy for an interview, but naming it shows you know the divide-and-conquer analysis does not stop at the master theorem. The interview-grade behaviour is to check the form *first*, in one sentence, before reaching for the cases. Candidates who lead with "this is not of the form a·T(n/b) + f(n) because the size shrinks by subtraction, so I'll unroll it" have already answered the real question being asked.
- What does T(n) = T(n-1) + O(1) solve to?Θ(n): there are n calls and each does constant work, so the sum is linear. It is also Θ(n) in stack space, since the calls nest n deep. Candidates who pattern-match the single recursive call to the halving case and answer Θ(log n) have skipped the only question that matters — how fast the input shrinks.
- Can the master theorem handle T(n) = T(n/3) + T(2n/3) + O(n)?No — the form allows a subproblems all of the same size n/b, and this one has two subproblems of different sizes. The answer is Θ(n log n): every level does Θ(n) work and the depth sits between log₃ n and log₁.₅ n, both Θ(log n). Akra-Bazzi is the general tool for unequal splits like this.
- Is T(n) = 2T(n/2) + n·log n also outside the theorem?It is of the right form, but no case covers it. The watershed is n, and n·log n exceeds it by only a logarithmic factor, so case 3's requirement of a polynomial gap fails while case 2's requirement of equality fails too. The true answer is Θ(n·log²n). This is a gap between the cases, not a violation of the form.
saying these in an interview costs you the question
- Applies the theorem with b = 1
- Calls T(n) = T(n-1) + O(n) a case 3 recurrence
- Says T(n) = T(n-1) + O(1) is logarithmic
- Forgets that depth n means Θ(n) stack space
- Treats unequal split sizes as close enough to the form