← O(n²) — quadratic complexity
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
1
+
# O(n²) — quadratic complexity
2
+
3
+
Now this is slow. Algorithms with O(n²) have nested loops, and the execution time grows quadratically with the size of the input.
4
+
5
+
## Example: bubble sort
6
+
7
+
```php
8
+
function bubbleSort($array) {
9
+
$n = count($array);
10
+
for ($i = 0; $i < $n - 1; $i++) {
11
+
for ($j = 0; $j < $n - $i - 1; $j++) {
12
+
if ($array[$j] > $array[$j + 1]) {
13
+
$temp = $array[$j];
14
+
$array[$j] = $array[$j + 1];
15
+
$array[$j + 1] = $temp;
16
+
}
17
+
}
18
+
}
19
+
return $array;
20
+
}
21
+
```
22
+
23
+
Every element is compared with every other — hence quadratic complexity. If the array has 1000 elements, that's up to a million operations.
24
+
25
+
:::warning
26
+
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.
27
+
:::
28
+
29
+
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?
30
+
31
+
← [Previous: O(n log n) — linearithmic complexity](/articles/from-tg/series/algorithm-complexity/o-n-log-n) · [Whole series](/articles/from-tg/series/algorithm-complexity) · [Next: O(n³) — cubic complexity →](/articles/from-tg/series/algorithm-complexity/o-n3)
32
+
33
+
---
34
+
35
+
*First published in Ukrainian in the Telegram channel [“Created to die”](https://t.me/php_while_true/42) on June 24, 2025.*