Quadratic Time On²

Quadratic Time O(n²)

Imagine you walk into a room of n people and you want every person to shake hands with every other person. The first person shakes n−1 hands, the next shakes n−2 new hands, and so on. As the room grows, the number of handshakes doesn't just grow — it grows much faster than the room does. Double the guests and you roughly quadruple the handshakes. That runaway feeling — work exploding faster than the input — is the intuition behind quadratic time.

The tell-tale structural sign in code is a loop nested inside another loop, where both loops range over the same input of size n. For each of the n outer steps, you do n inner steps, giving you n × n = n² units of work.

Precise definition

An algorithm runs in quadratic time when its running time T(n) grows proportionally to the square of the input size: T(n) = O(n²). Formally, T(n) is O(n²) if there exist positive constants c and n₀ such that T(n) ≤ c·n² for all n ≥ n₀.

Big-O keeps only the dominant term and drops constant factors. So 3n² + 50n + 200 is still O(n²): once n is large, the n² term swamps everything else, and the leading 3 doesn't change the growth shape. This is why the handshake count — exactly n(n−1)/2 = ½n² − ½n — is O(n²) despite the ½ and the linear tail.

Quadratic sits above linear (O(n)) and log-linear (O(n log n)) but below cubic (O(n³)) and the exponential classes. It is the classic signature of brute-force pairwise comparison.

Worked example: counting operations in bubble sort

Let's sort the array [5, 1, 4, 2] (n = 4) with bubble sort and count the key operation — the comparison. Bubble sort makes n−1 passes; each pass walks the unsorted prefix comparing adjacent pairs.

• Pass 1 compares 3 pairs: (5,1)→swap, (5,4)→swap, (5,2)→swap → [1,4,2,5]
• Pass 2 compares 2 pairs: (1,4)→ok, (4,2)→swap → [1,2,4,5]
• Pass 3 compares 1 pair: (1,2)→ok → [1,2,4,5]

Total comparisons = 3 + 2 + 1 = 6. In general that sum is (n−1) + (n−2) + … + 1 = n(n−1)/2. For n = 4 that is 4·3/2 = 6 — matching our count exactly. For n = 1000 it is 499,500 comparisons; bump the input to n = 2000 and it jumps to 1,999,000 — ~4× the work for 2× the data. That multiplier is the fingerprint of O(n²).

Best / worst / average. The comparison count above is fixed by the loop structure, so it is Θ(n²) in all cases. But an optimized bubble sort with an early-exit flag is O(n) in the best case (already-sorted input: one clean pass, zero swaps), while worst and average stay Θ(n²). Always name the case you mean.

Common pitfalls & what an interviewer probes

• Nested loops aren't automatically O(n²). What matters is how many times the inner body runs. If the inner loop is bounded by a constant, or iterates over a different, small set, it's not n². Interviewers love asking you to justify the bound, not just count braces.
• Two loops in sequence are O(n), not O(n²). Additive work (for..; for..) gives n + n = O(n). Only nested (multiplicative) loops square it. Confusing + with × is a classic slip.
• Hidden quadratics. Calling an O(n) operation inside an O(n) loop — e.g. list.contains(), string concatenation in a loop, or repeated arr.remove(0) — silently costs O(n²) even with a single visible loop. Probing for these is a favourite trap.
• i < j triangular loops are still O(n²). Doing only n(n−1)/2 pairs feels cheaper, but halving is a constant factor — the class is unchanged. Expect the interviewer to reject “it's faster so it's O(n log n)”.
• The real question: “Can you do better?” For pairwise problems the escape hatch is usually a hash set/map (trade space for time → O(n)) or sorting first (→ O(n log n)). Naming that pivot is what they're listening for.

When it matters & trade-offs vs neighbours

Quadratic algorithms are perfectly fine when n is small or bounded. For n ≤ a few thousand, an O(n²) pass finishes in microseconds-to-milliseconds, and a simple double loop is often more readable and cache-friendly than a clever alternative. Insertion sort (O(n²)) even beats O(n log n) sorts on tiny or nearly-sorted arrays, which is why real libraries switch to it for small partitions.

The danger is scale. At n = 1,000,000, O(n²) is ~10¹² operations — minutes to hours — while O(n log n) is ~2×10⁷ (sub-second) and O(n) is ~10⁶ (instant). The gap widens without bound, so a quadratic solution that passes small tests can fall off a cliff in production.

• vs O(n) / O(n log n): These usually cost extra memory (a hash map) or a preprocessing step (sorting). If n is large or growth is expected, pay that cost. If n is capped and small, quadratic's simplicity can win.
• vs O(n³): Cubic (e.g. naive matrix multiply, triple-nested loops) degrades even faster; the same “add a hash map / restructure” instincts often knock a dimension off.

Rule of thumb for interviews: if the input can exceed ~10⁴–10⁵, an O(n²) answer likely won't pass time limits — treat it as a correct baseline to then optimize, not the final answer.

Key takeaways

• Definition: work grows as the square of input — T(n) = O(n²); the fingerprint is doubling n roughly quadrupling the work.
• Structural sign: genuinely nested loops over the same n, or an O(n) operation hidden inside an O(n) loop — but always justify the bound, not just count loops.
• Escape hatches: a hash set/map trades space for O(n); sorting first gives O(n log n). Naming the pivot is the interview signal.
• Practicality: fine and even preferable for small/bounded n (insertion sort), disastrous at large n — use it as a correct baseline to optimize from.