For an arbitrary-precision multiply with T(n)=3T(n/2)+O(n), what does the master theorem give and when does it actually beat the quadratic method?
answer
- Count the recursive multiplies, not the additions
- a = 3 and b = 2 set everything
- Watershed is n to the log base 2 of 3
- The linear combine is polynomially smaller
- Exponent near 1.585, leaves dominate
basics
~20 sIt solves to Θ(n^(log_2 3)), about Θ(n^1.585), by case 1: the watershed beats the linear combine, so the leaves dominate. It outruns the quadratic schoolbook method only above a crossover size, because its constants, temporaries and call overhead are far larger.
solid answer
~50 sRead the parameters off the routine: three recursive multiplies of half-length operands means a = 3 and b = 2, and the additions, shifts and subtractions that stitch the results together are Θ(n). The watershed is `n^(log_2 3)` ≈ n^1.585, and the linear f(n) is polynomially smaller, so case 1 gives **Θ(n^1.585)** — asymptotically better than the Θ(n^2) schoolbook method. The exponent comes entirely from the pair (3, 2): the naive split does four half-size multiplies, giving `n^(log_2 4)` = n^2 and no win at all, so the whole gain is one eliminated subproblem, not a faster combine. In production that asymptotic win only shows up above a crossover — commonly a few dozen machine words — so real big-number code hard-codes a cutoff below which it calls the simple quadratic routine, and switches again to Toom-Cook or transform-based methods at very large sizes.
code
pseudocode · 13 linesBIG-MULTIPLY(x, y, n)
if n <= CUTOFF
return SCHOOLBOOK(x, y, n)
m = n / 2
xhi = high(x, m)
xlo = low(x, m)
yhi = high(y, m)
ylo = low(y, m)
p1 = BIG-MULTIPLY(xhi, yhi, n - m)
p2 = BIG-MULTIPLY(xlo, ylo, m)
p3 = BIG-MULTIPLY(xhi + xlo, yhi + ylo, m + 1)
mid = p3 - p1 - p2
return p1 * base^(2*m) + mid * base^m + p2go deeper
Be able to count the recursive calls and the division factor in a routine and write down the recurrence. Recognising that three half-size calls give a smaller exponent than four is enough at this level.
Compute n^(log_2 3) ≈ n^1.585, name it as case 1, and explain that the linear stitching never appears in the answer because the leaves dominate.
Show that you would keep the quadratic path below a measured cutoff, that you find the crossover by benchmarking rather than deriving it, and that a lower exponent alone never justifies shipping the more complex routine.
Own the call on whether the workload ever reaches the sizes where this pays: a lower exponent that never activates at production operand lengths is complexity, review burden and a subtle-bug surface bought for nothing, and saying no to it is the correct answer more often than not.
## Reading the recurrence off the routine The fragment splits each n-digit operand into a high half and a low half, makes **three** recursive multiplies of roughly half-length operands, and reassembles the product with additions, subtractions and shifts. So: - **a = 3** — three recursive calls. - **b = 2** — each call's operands are about half as long. - **f(n) = Θ(n)** — additions, subtractions and digit shifts over n-digit numbers are linear. That is `T(n) = 3T(n/2) + Θ(n)`. ## Applying the theorem The watershed is `n^(log_b a) = n^(log_2 3) ≈ n^1.585`. Compare with f(n) = Θ(n): is n polynomially smaller than n^1.585? Yes — `n = O(n^(1.585 − ε))` with ε = 0.5, comfortably. That is **case 1**, so ``` T(n) = Θ(n^(log_2 3)) ≈ Θ(n^1.585) ``` and f(n) does not appear in the answer at all. The recursion tree grows downward: level k has 3^k calls on operands of length n/2^k, so per-level cost is (3/2)^k · n, increasing until the leaves, where roughly n^1.585 base cases sit. ## Where the win comes from — and where it does not The naive split of a multiplication into halves needs four half-size products. That recurrence is `T(n) = 4T(n/2) + Θ(n)`, watershed `n^(log_2 4) = n^2` — case 1 again, answer Θ(n^2), which is exactly the schoolbook cost. Splitting bought nothing. The trick is algebraic: the two middle products can be recovered from a single extra multiply of the two half-sums, minus the two products you already have. Three multiplies replace four, and the exponent drops from log₂4 = 2 to log₂3 ≈ 1.585. This is the practical lesson of case 1, and it is why the interviewer asks: **in a leaf-dominated recurrence the exponent is a function of (a, b) alone.** Making the linear combine twice as fast changes a constant and nothing else. Eliminating one of the recursive calls changes the exponent. Engineers who have internalised the case know which of those two optimisations to fund. | split strategy | recurrence | exponent | result | |---|---|---|---| | four half-size products | 4T(n/2) + Θ(n) | log₂4 = 2 | Θ(n^2) | | three half-size products | 3T(n/2) + Θ(n) | log₂3 ≈ 1.585 | Θ(n^1.585) | | five third-size products | 5T(n/3) + Θ(n) | log₃5 ≈ 1.465 | Θ(n^1.465) | ## Why the asymptotic answer is not the whole decision Big-O is an upper bound on growth, and growth is not runtime. Three facts decide whether the recursive method is worth shipping: 1. **Constants dominate at small sizes.** Each level does several full-length additions, subtractions and shifts, plus call overhead and temporary storage. The schoolbook method is a tight double loop with excellent locality and no allocation. For operands of a handful of words the simple method wins by a wide margin, and it wins for the sizes most applications actually see — a ledger amount, a currency conversion, a checksum accumulator. 2. **The crossover is empirical, not derivable.** You find it by measuring both implementations across a range of operand lengths on the target hardware and reading off where the curves meet, then hard-coding that as a base-case cutoff. Mature big-number code carries such a threshold, often tuned per platform, and re-tunes when the hardware or the word size changes. 3. **The cutoff changes the constant, not the exponent.** Switching to the quadratic method below the threshold leaves the asymptotic class untouched — the base cases were always Θ(1) *relative to n's growth* — while cutting a large constant factor out of the deepest, most numerous levels. That is the same reasoning behind hybrid sorts that fall back to a simple method on short runs. ## Space and depth The recursion is Θ(log n) deep, so stack usage is trivial. Temporaries are the real cost: each call allocates operands of about half its own length. Because the calls run one at a time, only one root-to-leaf path is live, and those sizes halve geometrically, so peak temporary space stays Θ(n) — provided the implementation frees or reuses buffers as it unwinds. It is the allocation *traffic*, not the peak, that hurts, and it is a large part of why the crossover sits where it does. ## What a strong answer sounds like State the parameters, name the case, give n^(log₂3) with the approximate 1.585, explain that the gain came from eliminating a subproblem rather than from a faster combine, and then refuse to stop there: say that you would keep the quadratic path for small operands, measure the crossover on representative sizes, and check whether your workload ever reaches operands long enough for any of this to matter. A candidate who reports only the exponent has answered the arithmetic; a candidate who reports the crossover has answered the engineering question.
- What would splitting into four half-size products instead of three give?T(n) = 4T(n/2) + Θ(n), watershed n^(log_2 4) = n^2, case 1, so Θ(n^2) — exactly the schoolbook cost with extra overhead on top. The recursive structure alone buys nothing; the entire gain comes from recovering the two middle products with one extra multiply instead of two.
- Would splitting each operand into thirds with five products be better still?Asymptotically yes: T(n) = 5T(n/3) + Θ(n) gives n^(log_3 5), about n^1.465. But each level's stitching is considerably more elaborate, so its crossover sits much higher, and it only pays on operands far longer than the three-product method's threshold. Production big-number code layers these, each with its own measured cutoff.
- How would you actually find the crossover point?Benchmark both implementations across a sweep of operand lengths using representative values, on the hardware you deploy to, and read off where the curves cross; then hard-code that length as the base-case cutoff. Re-measure after a compiler, hardware or word-size change — the threshold is a property of the machine, not of the algorithm.
Trading four full-price items for three plus a bit of arithmetic only pays once the basket is large enough that the arithmetic is cheaper than the item you skipped.
saying these in an interview costs you the question
- Says three half-size calls plus linear work is O(n log n)
- Reads log base 2 of 3 as 1.5
- Assumes the asymptotic win holds at every operand size
- Claims a faster combine step would lower the exponent
- Treats the base-case cutoff as changing the complexity class