Time Complexity (Big O)

Also Known As

TL;DR

Explanation

Big O notation characterises the worst-case growth rate of an algorithm. O(1) constant time (hash table lookup), O(log n) logarithmic (binary search), O(n) linear (single pass), O(n log n) linearithmic (merge sort), O(n²) quadratic (nested loops), O(2ⁿ) exponential (naive recursive Fibonacci). PHP developers commonly introduce O(n²) accidentally by nesting foreach loops over large arrays or running queries inside loops. Understanding complexity guides correct data structure choice and prevents scalability cliffs.

Common Misconception

Why It Matters

Common Mistakes

• Nested loops over the same data — O(n²) that could be O(n) with a hash map.
• Using in_array() in a loop — O(n) per call makes the loop O(n²); flip the array for O(1) lookups.
• Sorting inside a loop — sort() is O(n log n); sorting once before the loop is correct.
• Not considering input size growth — code that's fast on dev data can be catastrophically slow on production volumes.

Code Examples

// O(n²) — nested loop over the same array
$hasDuplicates = false;
for ($i = 0; $i < count($arr); $i++) {
    for ($j = $i + 1; $j < count($arr); $j++) {
        if ($arr[$i] === $arr[$j]) { $hasDuplicates = true; break 2; }
    }
}

// O(n) — hash map lookup
$seen = [];
$hasDuplicates = false;
foreach ($arr as $v) {
    if (isset($seen[$v])) { $hasDuplicates = true; break; }
    $seen[$v] = true;
}

// Or one-liner:
$hasDuplicates = count($arr) !== count(array_unique($arr));

References

• ↗ https://en.wikipedia.org/wiki/Big_O_notation

Tags

Related Terms