Misusing big O: constants and preconditions decide more than the order

Comparing two implementations by big O only holds within one range of input sizes. Outside it, constants, memory locality and branch prediction matter more than the order itself.

Small n favors the lower order

Insertion sort is O(n²) and quicksort is O(n log n). At n = 10 insertion sort usually wins: no recursion, no partition overhead, sequential array access.

Standard libraries do exactly this: switch to insertion sort on small ranges and only then use quicksort.

n = 10     insertion sort 2x faster
n = 1000   quicksort 20x faster

So “never use O(n²)” is wrong. Ask for the actual upper bound on n first.

O(1) does not mean fast

A hash lookup is amortized O(1) and a linear array scan is O(n). At n = 8 the array often wins: one cache line read versus hashing plus probing.

Linked lists are the extreme case. An O(1) insert in theory, yet traversing one is an order of magnitude slower than an array because every step chases a pointer. Big O says nothing about memory layout.

Preconditions are the real story

The O(1) of a hash table assumes a uniform hash. An attacker can craft colliding keys and degrade lookups to O(n). That is not theoretical; it is a common denial-of-service vector.

Structure	Claim	Precondition
Hash table	O(1)	uniform, unpredictable hash
Quicksort	O(n log n)	average case, good pivots
Dynamic array append	amortized O(1)	geometric growth
B-tree lookup	O(log n)	no extreme key skew

How to actually compare

1. Measure first. Optimizing without a profile is guessing.
2. Use real input sizes. Ten and a hundred thousand can invert the answer.
3. Look at constants. Two implementations of the same order differing 5x is normal.
4. Look at memory. A cache miss usually costs more than a few extra arithmetic ops.

Big O answers how much slower things get when data doubles. It does not answer which one is faster. Keep the questions apart.