Big O Notation: What It Actually Measures (And What It Doesn't)

Big O notation is one of those concepts that is easy to memorize and easy to misapply.

Most developers learn it as a label: O(1) is fast, O(n²) is slow, O(log n) is somewhere in the middle. That framing is useful enough to pass a quiz. It breaks down the moment you try to use it to make real performance decisions.

What Big O Actually Describes

Big O is not a speed measurement. It is a description of how an algorithm's cost grows as the input size grows.

Formally, it captures the upper bound of that growth rate. When we say an algorithm is O(n), we mean: as n gets large, the number of operations grows at most linearly. The exact coefficient does not matter. Whether it does 3n + 5 operations or 100n + 12, both are O(n) because they grow at the same rate.

That last part is worth slowing down on. Big O notation deliberately strips away the constant multiplier. Two algorithms can both be O(n) and yet one can be fifty times slower than the other at any practical input size. The notation does not capture that. It was never designed to.

What it does capture is the shape of growth. A linear algorithm stays manageable as data doubles. A quadratic one starts to hurt. An exponential one falls apart entirely. Big O is a tool for reasoning about scale, not a timer.

O(1) Means Constant, Not Cheap

Constant time means the cost does not change with input size. It does not mean the cost is small.

An algorithm can do a fixed million operations every time it runs and still be O(1). A different algorithm that does ten operations linearly is O(n). For any input smaller than a million elements, the O(n) algorithm will finish faster.

This is not a contrived edge case. It shows up in real systems regularly.

A Concrete Example: Hash Map vs. Array Scan

Hash map lookup is the classic O(1) example. You compute a hash, land on a bucket, and retrieve the value. Constant time regardless of how many keys the map holds.

Array linear search is O(n). You walk elements one by one until you find a match.

The conventional wisdom is that the hash map wins. For large inputs, it does. But for small inputs, the picture often flips.

Here is why. A hash map lookup involves several steps that do not show up in the Big O label:

• Computing the hash of the key
• Applying a modulo to find the bucket index
• Following a pointer to the actual value (or chain of values if there are collisions)

Each of those steps has real cost. And because the data is not laid out contiguously in memory, you are likely to see cache misses as the CPU fetches from different memory locations.

An array of five or ten elements fits in a single cache line. Walking it is cheap. Each comparison is fast, the data is physically adjacent, and there is no pointer chasing. For small n, the O(n) scan beats the O(1) map in practice.

This is not theoretical. V8, the JavaScript engine in Node.js and Chrome, uses linear search for objects with very few properties before switching to a hash-based representation. The Go standard library does the same in parts of its runtime. Engineers who have measured both approaches made this call because the data showed it was the right one.

// For a tiny known-size lookup, a direct scan can outperform a Map
const STATUS_CODES = [
    { code: 200, label: "OK" },
    { code: 201, label: "Created" },
    { code: 404, label: "Not Found" },
    { code: 500, label: "Internal Server Error" },
];
 
// O(n), but n is always 4. Cache-friendly and no hash overhead.
function getLabel(code: number): string | undefined {
    return STATUS_CODES.find((s) => s.code === code)?.label;
}

For a fixed four-element list, the scan is not a performance problem. It is the correct choice.

The Crossover Point

Every pair of algorithms with different Big O classes has a crossover point: the input size at which the slower-complexity algorithm becomes worse. Below that threshold, the one with the "worse" complexity can still win on raw speed because its constant factor is lower.

This is why algorithm textbooks often mention that sorting libraries use insertion sort (O(n²)) for small subarrays even inside merge sort (O(n log n)). The constant factor for insertion sort is so low at small sizes that the asymptotically better algorithm loses until n grows enough for the difference in growth rate to matter.

The practical lesson: Big O tells you what happens at scale. It does not tell you which algorithm wins at your actual input size.

Wrap Up

Big O measures growth rate, not speed. Constants matter. Cache behavior matters. Memory access patterns matter. None of those appear in the notation.

O(1) is still a useful signal. Constant-time operations do not degrade as data grows, and that property is valuable. But "constant time" is not a synonym for "fast." An O(1) algorithm with high constant cost can lose to an O(n) algorithm on the inputs you actually process.

The habit worth building is this: reach for Big O to reason about how things scale, then profile and measure when actual performance matters. The notation narrows the search space. It does not replace the measurement.