O(n²) — quadratic complexity

← O(n²) — quadratic complexity

Ashterix

docs: English JsonRpcBundle docs, REST and MCP Bundle sections, package cards

en/articles/from-tg/series/algorithm-complexity/o-n2.md new file +35 −0

O(n²) — quadratic complexity

Now this is slow. Algorithms with O(n²) have nested loops, and the execution time grows quadratically with the size of the input.

Example: bubble sort

function bubbleSort($array) {
    $n = count($array);
    for ($i = 0; $i < $n - 1; $i++) {
        for ($j = 0; $j < $n - $i - 1; $j++) {
            if ($array[$j] > $array[$j + 1]) {
                $temp = $array[$j];
                $array[$j] = $array[$j + 1];
                $array[$j + 1] = $temp;
            }
        }
    }
    return $array;
}

Every element is compared with every other — hence quadratic complexity. If the array has 1000 elements, that's up to a million operations.

Any nested loop is a warning sign. In real code, O(n²) shows up when comparing everything with everything: for example, filtering intersections, duplicates, aggregations without indexes.

Sometimes you can't avoid O(n²), but as soon as you see a double loop, it's worth at least asking yourself: isn't there a better way?

← Previous: O(n log n) — linearithmic complexity · Whole series · Next: O(n³) — cubic complexity →

First published in Ukrainian in the Telegram channel “Created to die” on June 24, 2025.