Big-O notation — time and space complexity mental model
Concept
Big-O notation describes how the running time (or memory) of an algorithm scales as the input size n grows. It focuses on the dominant term and ignores constants and lower-order terms.
Why it matters: An O(n²) algorithm on n=10 takes 100 steps. On n=10,000 it takes 100,000,000 steps. An O(n log n) algorithm on n=10,000 takes ~130,000 steps. Complexity class dominates at scale.
Common complexity classes (from fastest to slowest):
O(1)— Constant: Always the same time regardless of n. Array index lookup, hash map get/set.O(log n)— Logarithmic: Time grows very slowly. Binary search, balanced BST operations. Halves the problem each step.O(n)— Linear: Time grows proportionally to n. Linear scan, array traversal.O(n log n)— Linearithmic: Efficient sorting (merge sort, quicksort average). Split + merge.O(n²)— Quadratic: Nested loops over the same data. Bubble sort, naive string comparison.O(2ⁿ)— Exponential: Each step doubles the work. Brute-force subset enumeration.O(n!)— Factorial: All permutations. Traveling salesman brute force. Impractical for n > 12.
Space complexity: Big-O also describes memory usage. A recursive algorithm that recurses n deep uses O(n) stack space even if it creates no additional data structures.
Best / Average / Worst: Big-O usually refers to worst case. Θ (theta) means average case. Ω (omega) means best case. In practice, say "worst case" or "average case" explicitly.
Amortized: A single operation occasionally takes O(n) (e.g., array resize), but averaged over many operations it's O(1). PHP array append is O(1) amortized.
Code Example
<?php
// O(1) — constant time — no matter the size of $arr
function getFirst(array $arr): mixed { return $arr[0] ?? null; }
// O(log n) — binary search (halves the search space each step)
function binarySearch(array $sorted, int $target): int
{
$left = 0; $right = count($sorted) - 1;
while ($left <= $right) {
$mid = intdiv($left + $right, 2);
if ($sorted[$mid] === $target) return $mid;
if ($sorted[$mid] < $target) $left = $mid + 1;
else $right = $mid - 1;
}
return -1;
}
// O(n) — linear scan
function linearSearch(array $arr, int $target): int
{
foreach ($arr as $i => $val) {
if ($val === $target) return $i;
}
return -1;
}
// O(n log n) — merge sort (see eng-08-002 for implementation)
// usort($arr, fn($a, $b) => $a - $b); — PHP uses Timsort, O(n log n)
// O(n²) — bubble sort (naive, avoid in production)
function bubbleSort(array $arr): array
{
$n = count($arr);
for ($i = 0; $i < $n - 1; $i++) {
for ($j = 0; $j < $n - $i - 1; $j++) { // inner loop — O(n) per outer iteration
if ($arr[$j] > $arr[$j + 1]) {
[$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]];
}
}
}
return $arr;
}
// Common PHP operations and their complexity:
// isset($arr[$key]) → O(1) — hash lookup
// in_array($v, $arr) → O(n) — linear scan (use isset on a flipped array for O(1))
// array_search($v, $arr) → O(n) — linear scan
// array_unique($arr) → O(n log n) — sorts then deduplicates
// array_flip($arr) → O(n)
// array_merge($a, $b) → O(n+m)
// sort($arr) → O(n log n) — Timsort
// count($arr) → O(1) — PHP caches array size
// Space complexity example
function sumArray(array $arr): int
{
$sum = 0; // O(1) space — just one variable
foreach ($arr as $v) $sum += $v;
return $sum;
}
function copyArray(array $arr): array
{
return $arr; // O(n) space — creates a copy of n elements
}
// Recursive fibonacci — O(2^n) time, O(n) space (call stack depth)
function fib(int $n): int
{
if ($n <= 1) return $n;
return fib($n - 1) + fib($n - 2); // two recursive calls each time = exponential!
}