Time Complexity (Big O)
debt(d7/e5/b5/t5)
Closest to 'only careful code review or runtime testing' (d7). The detection_hints indicate automated detection is 'no', and while tools like blackfire, phpstan, and phpbench can help profile or benchmark, they don't automatically flag algorithmic complexity issues — a developer must interpret profiling results or manually review code patterns like nested loops and in_array inside loops. There is no compiler or linter that reliably catches O(n²) vs O(n) choices.
Closest to 'touches multiple files / significant refactor in one component' (e5). The quick_fix advises profiling first, but common_mistakes show the actual remediation — replacing nested loops with hash maps, flipping arrays for O(1) lookups, moving sorts outside loops — requires understanding data flow and may touch multiple functions or files. It's more than a one-line swap but less than a cross-cutting architectural change.
Closest to 'persistent productivity tax' (b5). The applies_to covers both web and cli contexts, meaning poor algorithmic choices can affect multiple code paths. The concept imposes an ongoing cognitive load on maintainers — every future change to data-processing code must consider input size growth — but it doesn't define the entire system's shape or impose a strong gravitational pull across all layers.
Closest to 'notable trap (a documented gotcha most devs eventually learn)' (t5). The misconception field explicitly states the trap: developers believe O(n²) is always too slow for production, when in fact the practical impact depends entirely on n. This is a well-documented gotcha — premature optimisation is a classic mistake — but it doesn't contradict how similar concepts work elsewhere or reliably cause catastrophic misuse.
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));