In a pairwise cross-check whose inner loop starts at i+1, why is the cost still O(n^2)?
answer
- count the inner trips for each i
- inner range shrinks by one each pass
- sum n-1 down to 1
- that sum is n(n-1)/2
- half of a quadratic is still quadratic
basics
~20 sStarting the inner loop at i+1 checks each unordered pair once instead of twice, so the body runs n(n-1)/2 times rather than n^2. That halves the work, but half of a quadratic is still quadratic.
solid answer
~40 sThe inner loop's trip count depends on the outer index: it runs `n-1` times, then `n-2`, down to `1`. Summing that arithmetic series gives `n(n-1)/2`, the triangular sum — roughly `n^2/2` comparisons. Skipping the mirrored pairs genuinely halves the constant factor, but big-O reports growth class, and `n^2/2` grows exactly as fast as `n^2`, so the bound stays Θ(n^2). As a reviewer that is the number worth saying out loud: at 300 transactions in a batch this is about 45,000 comparisons and invisible; at 30,000 it is about 450 million and the batch window is gone. The shape to recognise is a dependent inner bound producing a triangular rather than rectangular iteration space — same class, half the constant.
code
pseudocode · 8 linesfor i in 0..n-1
for j in i+1..n-1
if card(tx[i]) == card(tx[j])
if minutes_between(tx[i], tx[j]) < 5
flag_pair(i, j)
// inner body runs (n-1) + (n-2) + ... + 1
// = n(n-1)/2 timesgo deeper
Recall that the inner loop runs fewer times on each outer pass and that the totals form the sum n-1 down to 1. Be able to state that sum as n(n-1)/2.
Derive the triangular sum on the spot, by pairing terms or by the triangle-of-a-grid picture, and explain why dividing a quadratic by two leaves the class unchanged. Distinguish a decrementing inner bound from a halving one.
Turn the bound into numbers for the real batch size and say what happens at 10x volume. Recommend a concrete guard — a cap, an alert, or a different structure — rather than a generic warning about quadratics.
Set the standard for when a quadratic is acceptable in this codebase: what evidence bounds n, what monitoring proves the bound still holds, and whether a rewrite is worth its risk against a documented ceiling.
## The fragment and what it actually counts A pairwise cross-check compares every unordered pair of items exactly once — say, every pair of a day's card transactions, looking for the same card charged twice within minutes: ``` for i in 0..n-1 for j in i+1..n-1 compare tx[i] with tx[j] ``` When `i = 0` the inner loop runs `n-1` times; when `i = 1`, `n-2` times; and so on down to `1` and finally `0`. The total is `(n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2` This is the **triangular sum** (often written `n(n+1)/2` when the series runs from 1 to n). Two derivations are worth having ready. Pairing the first and last terms gives `(n-1) + 1 = n`, the second and second-last also `n`, and there are about `n/2` such pairs — hence `n^2/2`. Geometrically, the iteration space is the triangle above the diagonal of an n-by-n grid: half the rectangle's area. ## Why the halving does not change the class Big-O, and more precisely Θ, describes how cost **scales** with input size, deliberately ignoring constant multipliers. `n(n-1)/2 = n^2/2 - n/2`; the dominant term is `n^2/2`, and dividing a quadratic by two leaves a quadratic. Double the input and the work goes up roughly fourfold either way. So the honest statement is: **Θ(n^2), with a constant factor of about one half.** The misconception this question aims at is the belief that skipping half the pairs buys a better class — that the shrinking inner range "must" produce a logarithm, or even linearity. It does not. A logarithm appears when the remaining work is *divided* at each step (n, n/2, n/4, ...), which sums to about 2n. Here the remaining work is *decremented* (n-1, n-2, n-3, ...), which sums to about n^2/2. Divide-versus-decrement is exactly the distinction between a logarithmic loop and a triangular one, and it is worth naming explicitly, because both are described loosely as "the range shrinks each pass". The mirror-image error also exists: claiming the count is exactly `n^2`. The class is right, but the count is wrong by a factor of two, and a reviewer who quotes `n^2` comparisons will overstate the batch's real cost. ## Reading it from the reviewer's chair Suppose this fragment arrives in a change that cross-checks a day's transactions for duplicate charges. The useful review question is not "is quadratic bad" — it is **what is n, and what does n do next quarter**. | transactions in a batch | pair comparisons | |---|---| | 300 | ~45,000 | | 3,000 | ~4.5 million | | 30,000 | ~450 million | | 300,000 | ~45 billion | Each 10x in volume is a 100x in work. At the top of the table the batch no longer finishes, and no constant-factor tuning — not the i+1 trick, not a faster comparison — moves it back. That is the reviewer's actual finding: the code is fine today and the growth curve is the risk, so the bound belongs in a comment and the input size belongs behind a guard or an alert. It is equally a defect to block the change reflexively. If n is bounded by construction — a batch is capped at 500 by an upstream window — then Θ(n^2) with a 500 ceiling is 125,000 comparisons, entirely reasonable, and reaching for a more complicated structure adds risk for nothing. Complexity classes describe growth; the decision needs the growth *and* the realistic range of n. ## The generalisation worth carrying Whenever an inner bound depends on the outer index, do not guess — write the trip count as a sum and evaluate it. Three shapes cover most cases: a constant inner bound gives Θ(n); an inner bound that decrements gives the triangular Θ(n^2); an inner bound that halves gives Θ(n log n) for the loop nest. The nesting itself never decides the answer. Counting the innermost body's executions always does.
- Change the inner loop to compare each transaction only against the previous 10. What is the cost now?Θ(n). The inner loop's trip count is bounded by a constant, so the nest costs about 10n and the constant drops. This is the counter-example to "two nested loops means quadratic": nesting multiplies trip counts, and multiplying by a constant leaves the class linear. The nesting depth never decides the answer; the innermost body's execution count does.
- If the inner bound halved each pass instead of decrementing, what would the nest cost?Θ(n log n). A halving inner loop runs about log2(n) times, and it does so for each of the n outer iterations. The key distinction is divide versus decrement: dividing the remaining range gives a logarithm, decrementing it gives the triangular sum and a quadratic. Both are loosely described as "the range shrinks", which is why the sum must be written out.
- As the reviewer, n is 300 today. Do you block the change?Not on the number alone — 45,000 comparisons is nothing. The finding is the growth curve: every 10x in volume is a 100x in work, so the change is fine now and fails badly later. Ask what bounds n. If it is capped upstream, document the bound and approve; if it tracks business growth, require a guard or an alert before the batch window closes.
saying these in an interview costs you the question
- Says skipping mirrored pairs makes it O(n log n)
- Claims halving the pair count improves the complexity class
- Quotes the trip count as exactly n^2
- Treats a decrementing inner bound like a halving one
- Blocks any quadratic without asking what bounds n