Four Simple Rules
Turning "how many steps does this code do" into a Big O class takes four rules:
1. Keep the worst case — count the most steps the code can ever need.
2. Drop the constants — O(2n) and O(n/2) are both O(n).
3. Drop the smaller terms — O(n + n²) is O(n²).
4. Different inputs get different letters — two different arrays give O(a · b), not O(n²).
Each rule has one example below.
Rule 1: Keep the Worst Case
A linear search can get lucky: if the value sits at the front, one step is enough. Big O ignores the luck and describes the array's worst case — the value is last, or missing, and all n elements are checked.
So a linear search is O(n), even though it often finishes earlier. The worst case is the promise the algorithm can always keep.
Best case and worst case of a search
Searching for the first word takes 1 step. Searching for a missing word takes all 5. Big O keeps the 5: linear search is O(n).
Output: PHP script
<?php
function search(array $words, string $target): int {
$steps = 0;
foreach ($words as $w) {
$steps++;
if ($w === $target) {
break;
}
}
return $steps;
}
$words = ["one", "two", "three", "four", "five"];
echo 'best case ("one"): ', search($words, "one"), " step\n";
echo 'worst case ("six"): ', search($words, "six"), " steps\n";
Rule 2: Drop the Constants
A loop that visits every second element does n/2 steps. Half the work — but the shape of the growth is unchanged: double the input, double the steps.
Big O keeps only the shape, so O(n/2), O(n) and O(2n) are all the same class: linear.
Half the steps is still O(n)
The loop jumps by 2 and visits 4 of the 8 elements. If the array doubles, the steps double too — so n/2 steps is still linear growth, O(n).
Output: PHP script
<?php
$nums = [3, 1, 4, 1, 5, 9, 2, 6];
$steps = 0;
// Visit every second element: n/2 steps.
for ($i = 0; $i < count($nums); $i += 2) {
echo $nums[$i], " ";
$steps++;
}
echo "\n";
echo "elements: ", count($nums), " steps: ", $steps, "\n";
Rule 3: Drop the Smaller Terms
Code often mixes parts with different costs: a simple loop (n steps) followed by nested loops (n² steps). The total is n + n².
As n grows, the n² part swallows the rest — at n = 1000 it is a million steps against a thousand. Big O keeps only the fastest-growing term: O(n + n²) becomes O(n²).
n + n² steps
For 6 elements the simple loop adds 6 steps and the nested loops add 36 — 42 in total. The square term already dominates, and its lead only grows with n.
Output: PHP script
<?php
$nums = [1, 2, 3, 4, 5, 6];
$steps = 0;
// One simple loop: n steps.
foreach ($nums as $x) {
$steps++;
}
// A loop inside a loop: n * n steps.
foreach ($nums as $x) {
foreach ($nums as $y) {
$steps++;
}
}
echo "n = ", count($nums), "\n";
echo "n + n*n = ", $steps, "\n";
Rule 4: Different Inputs, Different Letters
When nested loops run over two different inputs, the step count is a · b — the two lengths multiplied. Calling that O(n²) would be wrong: the inputs can have very different sizes.
The honest class is O(a · b). It only becomes O(n²) in the special case where both inputs are the same one.
Two different arrays
3 colors times 2 animals is 6 steps. The complexity is O(a · b) — if the animals array grows and the colors array does not, only b matters.
Output: PHP script
<?php
$colors = ["red", "green", "blue"];
$animals = ["cat", "dog"];
$steps = 0;
foreach ($colors as $c) {
foreach ($animals as $a) {
$steps++;
}
}
echo "colors: ", count($colors), " animals: ", count($animals), "\n";
echo "steps: ", $steps, "\n";
The Limits of Big O
Big O is a rough tool on purpose, and it is worth knowing what it hides.
It only sees the worst case. An algorithm with a scary worst case can be excellent in practice if that case is rare. Sometimes the average case is the number that matters.
It ignores the constants. On paper, 1000 · n and n are the same class. For small inputs, a "slower" O(n²) algorithm with tiny steps can beat a "faster" O(n) one with heavy steps.
Use Big O to compare how algorithms scale. For real speed on real data, measure.