Big O for Memory
Big O can describe memory the same way it describes time: how much extra space does the algorithm need as the input grows?
We count only the extra space — the variables and arrays the algorithm creates — not the input itself. This extra space is called auxiliary space.
O(1) space: a fixed number of variables, no matter the input. O(n) space: something new is stored per input element, like a copy or an associative array of seen values.
O(1) Space
An algorithm that keeps only a few plain variables uses constant space. The array can hold ten elements or ten million — the algorithm itself still owns just its counters.
Summing, finding the maximum, and linear search are all O(n) time but O(1) space: they read a lot and remember almost nothing.
Sum with one variable
The whole algorithm remembers exactly one number, $sum. Its memory use does not grow with the array: O(1) space.
Output: PHP script
<?php
$nums = [3, 1, 4, 1, 5, 9, 2, 6];
// One extra variable, no matter how long the array is.
$sum = 0;
foreach ($nums as $n) {
$sum += $n;
}
echo "sum: ", $sum, "\n";
O(n) Space
As soon as the algorithm builds something with one entry per input element — a new array, an associative array — its space is O(n): double the input, double the memory.
That is not bad by itself. It is simply a cost you should notice, because it can be traded.
Build a new array
The output array gets one element for every input element. 5 in, 5 out — memory grows in step with the input: O(n) space.
Output: PHP script
<?php
$nums = [1, 2, 3, 4, 5];
// A new array with one element per input element.
$doubled = [];
foreach ($nums as $n) {
$doubled[] = $n * 2;
}
echo "input: ", implode(", ", $nums), "\n";
echo "output: ", implode(", ", $doubled), "\n";
Trading Space for Time
Often you can spend memory to save time. The classic example is Two Sum: find two numbers in an array that add up to a target.
The direct way checks every pair — O(n²) time, O(1) space. The fast way walks the array once and remembers every number it has seen as a key in an associative array. For each number it asks: "have I already seen target - n?" — O(n) time, O(n) space.
This trade is usually worth it: memory can be added to a machine, time cannot.
Two Sum with two loops
Every pair is checked until a match appears — up to 15 checks for 6 elements, and the count grows with the square of the input. No extra memory is used.
Output: PHP script
<?php
$nums = [2, 11, 15, 1, 8, 7];
$target = 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] === $target) {
echo "found: ", $nums[$i], " + ", $nums[$j], " after ", $checks, " checks\n";
}
}
}
echo "total checks: ", $checks, "\n";
Two Sum with an associative array
One pass, 6 checks. Each number is looked up with isset() and stored in the $seen associative array — constant-time work per element. The array is the O(n) memory that buys the O(n) time.
Output: PHP script
<?php
$nums = [2, 11, 15, 1, 8, 7];
$target = 9;
$seen = [];
foreach ($nums as $n) {
$need = $target - $n;
if (isset($seen[$need])) {
echo "found: ", $need, " + ", $n, "\n";
}
$seen[$n] = true;
}
echo "checked ", count($nums), " elements once\n";