A Loop Inside a Loop
O(n²) means quadratic time: the work grows with the square of the input. Twice the elements, four times the steps. Ten times the elements, a hundred times the steps.
The tell-tale shape in code is a loop inside a loop, both running over the same data. The outer loop runs n times, and for each of those the inner loop runs n times again: n · n steps.
Quadratic is fine for small arrays. For 100,000 elements it is already 10 billion steps — that is where programs start to hang.
All Pairs
The most direct O(n²) task: combine every element with every element. 4 letters make 4 · 4 = 16 pairs; 100 letters would make 10,000.
Build every pair
The outer loop picks $x, the inner loop pairs it with every $y. 4 elements produce 16 pairs — the square of the input size.
Output: PHP script
<?php
$letters = ["a", "b", "c", "d"];
$pairs = 0;
foreach ($letters as $x) {
foreach ($letters as $y) {
echo $x . $y, " ";
$pairs++;
}
echo "\n";
}
echo count($letters), " elements made ", $pairs, " pairs\n";
Bubble Sort
Bubble sort is the classic quadratic algorithm: it repeatedly walks the array and swaps neighbours that are in the wrong order. Big values "bubble" to the end, one pass at a time.
With its two nested loops it makes about n²/2 comparisons. It is a great algorithm to learn from — and a bad one to use: PHP's built-in sort() does the same job in O(n log n).
Sort with two nested loops
Sorting 5 elements takes 4 + 3 + 2 + 1 = 10 comparisons. For 1,000 elements it would be about half a million — while an O(n log n) sort needs about ten thousand.
Output: PHP script
<?php
$nums = [5, 3, 8, 1, 4];
$comparisons = 0;
$n = count($nums);
for ($i = 0; $i < $n - 1; $i++) {
for ($j = 0; $j < $n - 1 - $i; $j++) {
$comparisons++;
if ($nums[$j] > $nums[$j + 1]) {
[$nums[$j], $nums[$j + 1]] = [$nums[$j + 1], $nums[$j]];
}
}
}
echo "sorted: ", implode(", ", $nums), "\n";
echo "comparisons: ", $comparisons, "\n";
Duplicates the Slow Way
Checking every element against every element that comes after it is another nested-loop pattern — comparing all pairs to find a duplicate.
It works, but it is O(n²). The Space Complexity page in this group shows the standard trick that makes this linear: remember the values you have already seen in an associative array.
Find a duplicate with two loops
Each element is compared with every later element. The duplicate pair of 1s is found after 7 checks; in the worst case — no duplicate at all — all 15 pair checks run.
Output: PHP script
<?php
$nums = [3, 1, 4, 1, 5, 9];
$checks = 0;
$n = count($nums);
for ($i = 0; $i < $n; $i++) {
for ($j = $i + 1; $j < $n; $j++) {
$checks++;
if ($nums[$i] === $nums[$j]) {
echo "duplicate: ", $nums[$i], " after ", $checks, " checks\n";
}
}
}