Big-O Notation

Also Known As

TL;DR

Explanation

Big-O expresses worst-case growth: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n^2) quadratic, O(2^n) exponential. The goal is to choose the lowest complexity class for the problem. O(1) operations (hash lookup, array index access) are always fast regardless of input size. O(n^2) operations (nested loops over the same data) become catastrophic at scale — 1000 items takes a million operations.

Diagram

graph TD
    subgraph Complexity_Growth
        O1["O(1) constant"]
        OLOG["O(log n) logarithmic"]
        ON["O(n) linear"]
        ONLOG["O(n log n) linearithmic"]
        ON2["O(n^2) quadratic"]
        O2N["O(2^n) exponential"]
    end
    O1 --> OLOG
    OLOG --> ON
    ON --> ONLOG
    ONLOG --> ON2
    ON2 --> O2N
    style O1 fill:#238636
    style OLOG fill:#238636
    style ON fill:#d29922
    style ONLOG fill:#d29922
    style ON2 fill:#f85149
    style O2N fill:#f85149

Common Misconception

Why It Matters

Common Mistakes

• Nested loops over the same collection — almost always O(n^2) or worse; usually fixable with a hash map.
• in_array() inside a loop — O(n^2) total; use array_flip + isset for O(n).
• Sorting inside a loop — sort() is O(n log n); sort once before the loop.
• Not considering space complexity alongside time complexity — an O(n) time algorithm may use O(n^2) memory.

Avoid When

• Comparing algorithms with identical Big-O complexity but vastly different constant factors — Big-O hides the practical runtime difference between O(n) with coefficient 2 versus coefficient 1000.
• Analyzing real-time systems or embedded devices where absolute latency bounds matter more than asymptotic growth — a O(n log n) sort that takes 50ms is worse than O(n^2) that takes 5ms for production constraints.
• Evaluating small, fixed-size inputs where Big-O analysis becomes meaningless — sorting 5 items offers no insight into whether you chose merge sort versus bubble sort.
• Assessing I/O-bound or memory-constrained operations where wall-clock time is dominated by disk/network access, not CPU cycles — Big-O ignores these system realities entirely.

When To Use

• Choosing between candidate algorithms for a new feature: compare their Big-O complexity to predict which will handle growth to target scale (e.g., 1M records) without rewrite.
• Identifying performance bottlenecks in production: if a service degrades nonlinearly with load, Big-O analysis reveals whether the culprit is O(n^2) logic that needs restructuring or acceptable O(n log n) behavior.
• Designing data structures for a system: decide between a hash table (O(1) lookup) versus a sorted array (O(log n) binary search) based on whether your workload prioritizes read speed or memory density.
• Code review or technical interview: quickly evaluate whether a proposed solution scales, especially catching nested loops or recursive calls that hide quadratic or exponential cost.

Code Examples

// O(n^2) — nested loop over same data:
foreach ($orders as $order) {
    foreach ($products as $product) {
        if ($order->product_id === $product->id) {
            // Found match
        }
    }
}

// O(n) — index products by ID first:
$productIndex = [];
foreach ($products as $p) $productIndex[$p->id] = $p;

foreach ($orders as $order) {
    $product = isset($productIndex[$order->product_id]) ? $productIndex[$order->product_id] : null;
}

Tags

🧠 Logic Engine

References

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