Why We Measure Algorithms
The same program runs fast on a new computer and slow on an old one. So seconds are a bad way to compare two algorithms — the number depends on the machine, not only on the code.
Instead we count steps: how many simple operations the algorithm does. A step is one small action, like reading a value, comparing two numbers, or adding them.
Big O notation describes how the number of steps grows when the input grows. It does not say "this takes 3 seconds". It says "if the input doubles, the work doubles" — that is O(n) — or "if the input doubles, the work stays the same" — that is O(1).
Big O looks at the worst case: the most steps the algorithm can ever need for an input of size n.
Counting Steps
A loop that visits every element of an array does one pass per element. For 5 elements that is 5 steps, for 10 elements 10 steps. The step count is the same as count($nums).
We do not care about the exact number. We care about the shape of the growth: twice the input, twice the steps. That shape is called linear, written O(n).
Count the steps of a loop
The function adds a $steps++ counter inside the loop. An array of 5 elements takes 5 steps, an array of 10 elements takes 10 steps — the count follows the input size.
Output: PHP script
<?php
function countSteps(array $nums): int {
$steps = 0;
$sum = 0;
foreach ($nums as $n) {
$sum += $n;
$steps++;
}
echo "sum: $sum\n";
return $steps;
}
$small = [2, 4, 6, 8, 10];
$big = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
printf("steps for 5 elements: %d\n", countSteps($small));
printf("steps for 10 elements: %d\n", countSteps($big));
Doubling the input doubles the work
The program runs the same counting loop for n = 100, 200 and 400. Every time n doubles, the step count doubles too. That is the fingerprint of O(n).
Output: PHP script
<?php
foreach ([100, 200, 400] as $n) {
$steps = 0;
for ($i = 0; $i < $n; $i++) {
$steps++;
}
printf("n = %3d -> %3d steps\n", $n, $steps);
}
The Growth Classes
Most algorithms fall into a few common growth classes, from fastest to slowest:
O(1) constant — the work never grows.O(log n) logarithmic — doubling the input adds only one step.O(n) linear — the work grows with the input.O(n log n) — a good sorting algorithm.O(n²) quadratic — a loop inside a loop.O(2ⁿ) exponential — the work doubles with every extra element.
For small inputs the difference is tiny. For big inputs it decides whether the program answers at once or never finishes.
Compare the growth classes
The table shows the step counts for growing n. At n = 16, log n is only 4 while 2ⁿ is already 65536. The bigger n gets, the more the classes drift apart.
Output: PHP script
<?php
printf("%5s %7s %5s %9s %6s %8s\n", "n", "log n", "n", "n log n", "n^2", "2^n");
foreach ([1, 2, 4, 8, 16] as $n) {
$logn = log($n, 2);
printf("%5d %7.0f %5d %9.0f %6d %8d\n", $n, $logn, $n, $n * $logn, $n * $n, 2 ** $n);
}
What Big O Ignores
Big O keeps only the shape of the growth and throws the details away. O(2n), O(n + 5) and O(n) are all the same class: linear.
Why? Because for big inputs the constant factor stops mattering. An algorithm that does 2 passes over a million elements is still in a different world than one that compares every element with every other element.
The exact rules for simplifying — drop the constants, drop the smaller terms — have their own page later in this group.
Two loops are still O(n)
The program does two separate passes over the array: one for the sum, one for the biggest value. That is 2n steps — 16 for 8 elements. Big O drops the constant 2, so this is still O(n).
Output: PHP script
<?php
$nums = [3, 1, 4, 1, 5, 9, 2, 6];
$steps = 0;
$sum = 0;
foreach ($nums as $n) {
$sum += $n;
$steps++;
}
$max = $nums[0];
foreach ($nums as $n) {
if ($n > $max) {
$max = $n;
}
$steps++;
}
echo "sum: $sum\n";
echo "max: $max\n";
echo "elements: ", count($nums), "\n";
echo "steps: $steps\n";