But what about Big-O?

Big-O notation usually gives asymptotic complexity for a particular algorithm. But it’s important to account for 3 factors when choosing the best data structure.

1. The constant

O(log N) complexity means C1 * log(N). And O(N) means C2 * N. It’s obvious that for certain C1, C2, and N, the O(N) algorithm will outperform the O(log N) algorithm. Often the N is capped at some reasonable and very modest maximum, and below that max N, the O(N) algorithm would outperform an algorithm with lower theoretical Big-O.

2. The worst-case

The asymptotic complexity is good for throughput planning. But there are worst-case scenarios like O(n²) for a usually O(n log n) Quicksort, or O(n) with a huge constant for a usually O(1) hash table insert (when hashtable is reallocated to grow). These directly affect the tail latency of some operations, where the unfortunate operations that hit the worst-case algorithm scenario would be significantly slower.

3. The hardware

I’ve heard a funny saying: “Cache is RAM, RAM is Disk, Disk is Tape, and Tape is Dead” 🙂.

It’s very important to appreciate how CPUs work with memory, and how data locality and CPU caching could influence performance by orders of magnitude.

An array of values (not references) that fits into L1 (or even L2) cache could be scanned linearly so quickly, that it would beat any fancy algorithm accessing data in memory spread over multiple pages.

The locality rules are simple: keep related data compact and together for the spatial locality, and access it from the same thread (reasonably expecting that it will be scheduled on the same CPU) for maintaining temporal locality. And don’t use primitives that flush CPU caches.