Why does Euclid's algorithm need only O(log min(a, b)) steps rather than roughly a/b?
answer
- The a/b estimate prices a different algorithm
- One remainder replaces a whole run of subtractions
- Compare a mod b against a/2
- Split on whether b exceeds half of a
- Slowest inputs are consecutive Fibonacci numbers
basics
~20 sOne remainder step collapses a whole run of subtractions. After the first swap each remainder is strictly less than half the dividend it came from, so the values shrink geometrically and the step count is logarithmic, not proportional to a/b.
solid answer
~50 sThe a/b estimate is the cost of the **subtraction** variant, which repeatedly takes `a - b`. The remainder step does all of those subtractions at once. The key bound: for `a >= b > 0`, `a mod b < a/2`. Two cases prove it — if `b <= a/2` then the remainder is below `b`, hence below `a/2`; if `b > a/2` then the quotient is 1 and the remainder is `a - b`, again below `a/2`. So each value is less than half the value two positions earlier in the sequence, giving at most about `2*log2(min(a, b))` division steps. The worst case is consecutive Fibonacci numbers, where every quotient is 1 and the sequence shrinks as slowly as it possibly can; Lamé's theorem bounds the steps at roughly five times the decimal digit count of the smaller input. So gcd on machine-word integers is a handful of operations, not thousands.
go deeper
Know that gcd via remainders is fast — a handful of steps even for large inputs — and that repeated subtraction is the slow way to do the same thing.
Derive the bound out loud: a mod b is always under a/2, by splitting on whether the divisor exceeds half the dividend, so the values shrink geometrically and the step count is logarithmic.
Add the precision that separates a good answer from a confident one: the bound counts division steps, those steps are constant-time only for machine-word integers, and the extremal inputs are consecutive Fibonacci numbers rather than large primes.
Be ready to judge when this cost stops being negligible — arbitrary-precision arithmetic in a hot path, or gcd inside an inner loop over millions of pairs — and what you would measure before optimising anything about it.
## Where the wrong estimate comes from "About a/b steps" is not a random guess — it is the exact cost of a different algorithm. The subtraction form of Euclid replaces `(a, b)` with `(a - b, b)` while `a > b`. To reduce `gcd(1000000, 3)` that way, you subtract 3 roughly 333,333 times before the first argument drops below the second. The remainder form replaces that entire run with one operation: `1000000 mod 3 = 1`, then `3 mod 1 = 0`, and it is done in two steps. Every candidate who quotes a/b is pricing the subtraction loop and attributing it to the division loop. ## The halving bound, in two cases Claim: for integers `a >= b > 0`, `a mod b < a/2`. - **Case `b <= a/2`.** A remainder is always strictly less than its divisor, so `a mod b < b <= a/2`. - **Case `b > a/2`.** Then `b` fits into `a` exactly once, so the quotient is 1 and `a mod b = a - b < a - a/2 = a/2`. There is no third case, so the bound is unconditional. Now look at the sequence of values the algorithm produces: `r0 = a`, `r1 = b`, `r2 = r0 mod r1`, `r3 = r1 mod r2`, and so on. The bound says every term is less than half the term **two positions before it**. After `2k` steps the leading value is below `a / 2^k`, and since the values are non-negative integers, the process must reach 0 within about `2*log2(a)` steps. Because the second step already brings both values at or below `min(a, b)`, the usual statement is `O(log min(a, b))` division steps. ## The extremal input Which inputs make it slowest? The algorithm is fast when quotients are large, because a large quotient means a big jump downward. The slowest possible run has every quotient equal to 1, meaning each step only subtracts once. Chase that requirement backwards from the terminating pair `(1, 0)` and you generate `1, 1, 2, 3, 5, 8, 13, ...` — the Fibonacci numbers. Consecutive Fibonacci numbers are therefore the worst case for a given magnitude, and this is the content of **Lamé's theorem**: the number of division steps never exceeds about five times the number of decimal digits of the smaller input. For values that fit in a machine word, that is on the order of tens of steps — which is why gcd is treated as effectively free inside a hot loop. A related consequence: the average number of steps is also logarithmic with a small constant, so there is no realistic input distribution that makes the division form behave badly. Unlike, say, a sorting algorithm whose worst case is reachable through adversarial input, Euclid's worst case is merely "a bit slower than typical", not a different complexity class. ## The precision the interviewer is listening for Three statements are commonly made slightly wrong, and each is worth getting exactly right: 1. **Big-O is an upper bound on step count, not a promise about wall time.** The `O(log min(a, b))` bound counts division steps. Each step is constant-time only when the numbers fit in machine words. For arbitrary-precision integers with thousands of digits, a single remainder operation is itself expensive, and the total cost has to be measured in bit operations rather than in steps. 2. **Halving is a bound, not a description.** Saying "the numbers halve each step" overstates it; the guarantee is that they at least halve across two steps, and typical inputs shrink far faster because quotients are usually larger than 1. 3. **The subtraction form is still correct.** It is not a wrong algorithm, just a slow one on skewed inputs. If you are asked to defend the mod form, defend it on cost, not on correctness. ## The argument to say out loud At a whiteboard, the compact version is three sentences: the remainder step performs every subtraction of a whole run in one operation; a remainder is always below half its dividend, because either the divisor is small enough that the remainder is smaller still, or the divisor is large enough that the quotient is 1; therefore the values shrink geometrically and the step count is logarithmic, with consecutive Fibonacci numbers as the slowest inputs. If someone then asks for a hard number, Lamé's five-times-the-digits bound is the one to quote.
- Which inputs of a given size force the maximum number of steps?Consecutive Fibonacci numbers. The algorithm is fast when quotients are large, so the slowest run is the one where every quotient is 1; working backwards from the terminating pair under that constraint generates the Fibonacci sequence. Lamé's theorem turns this into a bound: at most about five times the number of decimal digits of the smaller input.
- Is the subtraction-based variant wrong, or just slow?Just slow. gcd(a, b) = gcd(a - b, b) for a > b follows from the same divisor-set argument as the remainder step, so the result is correct. The cost is the problem: with a huge value and a tiny one it performs about a/b iterations, where the remainder form finishes in a couple of steps.
- Does the logarithmic bound still describe the cost for very large integers?It still bounds the number of division steps, but not the wall-clock cost. The step count is only a good proxy for time when each remainder operation is constant-time, which holds for machine-word integers. With thousands of digits each remainder is itself expensive, so the honest analysis counts bit operations rather than steps.
Subtraction pays a coin at a time; the remainder step hands over the whole stack and takes change once. The change is always less than half of what you handed over.
saying these in an interview costs you the question
- Quotes a/b steps, pricing the subtraction variant instead
- Claims the values halve exactly every single step
- Says the worst case is two large primes
- Treats the step count as constant-time regardless of integer width
- Calls the subtraction form incorrect rather than slow