Introduction

Big O notation describes growth, not exact runtime. That is why an O(N) algorithm can absolutely run slower than an O(N log N) algorithm on real machines, especially for moderate input sizes or when constant factors, memory access patterns, and implementation quality dominate the asymptotic term.

The mistake is treating complexity classes as a stopwatch. They are not. They answer "how does runtime scale?" rather than "which program is faster for the input I have today?"

Big O Hides Constant Factors

Suppose algorithm A is O(N) and performs a very expensive operation on each element, while algorithm B is O(N log N) but has tight loops, contiguous memory access, and library-grade implementation quality. For realistic values of N, B may still win.

If you write rough cost models:

T1(N) = 1000 * N
T2(N) = 10 * N * log2(N)

then for N = 1_000, the O(N) algorithm costs about 1_000_000 units, while the O(N log N) algorithm costs about 99_657 units. The lower asymptotic class loses because its constant is much worse.

Cache Locality Can Beat Better Asymptotics

Real hardware strongly rewards predictable, contiguous memory access. An algorithm that walks a flat array can be much faster than one that jumps through pointers, even if the pointer-heavy version has a better asymptotic story.

A classic example is deduplication. Sorting followed by a linear scan is O(N log N), yet it can outperform a supposedly O(N) hash-heavy approach because sorting implementations are deeply optimized and cache-friendly.

1#include <algorithm>
2#include <iostream>
3#include <unordered_set>
4#include <vector>
5
6std::size_t dedup_with_sort(std::vector<int> values) {
7    std::sort(values.begin(), values.end());
8    auto it = std::unique(values.begin(), values.end());
9    return static_cast<std::size_t>(it - values.begin());
10}
11
12std::size_t dedup_with_hash(const std::vector<int>& values) {
13    std::unordered_set<int> seen(values.begin(), values.end());
14    return seen.size();
15}

Neither complexity label alone tells you which function is faster on your platform, with your input distribution, allocator, and compiler.

Input Size Matters

Asymptotic analysis is about behavior as N grows large. For small or medium inputs, the logarithm term may barely matter. log2(1_000_000) is only about 20, which is much smaller than many constant-factor penalties.

That is why a library sort routine can beat an apparently simpler linear algorithm for the data sizes people actually process in day-to-day applications.

Implementation Quality Matters

Comparing O(N) versus O(N log N) only makes sense if the implementations are of comparable quality. In real projects, one version may be:

• written in optimized C or C++
• vectorized by the compiler
• parallelized internally
• heavily tuned over years

while the other version is:

• branch-heavy
• allocation-heavy
• written in a higher-level language
• full of cache misses

At that point, the asymptotic comparison is only part of the story.

Common Pitfalls

• Treating Big O notation as an exact timing model.
• Ignoring constant factors, allocations, and cache behavior.
• Comparing an optimized standard-library implementation with an unoptimized custom implementation and blaming complexity alone.
• Assuming the asymptotically better algorithm must win at the input sizes used in production.
• Benchmarking on unrealistic data distributions and drawing broad conclusions.

Summary

• 'O(N) can be slower than O(N log N) because Big O hides constants and hardware effects.'
• Cache locality, allocation behavior, and implementation quality matter a lot.
• The logarithm term grows slowly, so N log N is often competitive for practical input sizes.
• Complexity analysis predicts growth, not exact wall-clock time.
• When speed matters, benchmark representative workloads instead of relying on notation alone.