Account

What new tool do you want?

Developer Tools

Big-O Complexity Cheat Sheet

Time and space complexity of common data structures and sorting algorithms — average and worst cases in Big-O notation.

How to use

  1. 1Search for a data structure or algorithm.
  2. 2Compare average and worst-case costs to pick the right one.

Frequently asked questions

What does O(n log n) mean?

The work grows a little faster than linearly. Sorting a million items takes roughly 20 million steps — the best possible for comparison sorts.

Why is hash table lookup O(1) but worst case O(n)?

With a good hash function items spread out evenly. If many keys collide in one bucket, lookups degrade to scanning a list.

Is the lower Big-O always faster?

Not for small inputs. Constants matter — insertion sort (O(n²)) beats quicksort on tiny arrays, which is why real sorts mix both.

A worked example of why n log n matters

Sorting 1 million items with an O(n²) algorithm like bubble sort takes roughly 1,000,000² = 1 trillion comparisons. An O(n log n) algorithm like merge sort takes roughly 1,000,000 × log₂(1,000,000) ≈ 1,000,000 × 20 = 20 million comparisons — about 50,000 times fewer operations for the same input size. That gap is precisely why the table flags O(n log n) as "the best possible for comparison sorts": it's not an arbitrary target, it's a proven lower bound, and it's the entire reason production sorting algorithms (Python's Timsort, V8's Array.sort) are built around merge-sort-family techniques rather than simpler quadratic approaches.

Why Timsort's row looks different from Quicksort's

Notice Timsort's best case is listed as O(n), not O(n log n) like quicksort or merge sort — that's not an error, it's Timsort's actual headline feature. Timsort (used by Python's sort() and Java's Arrays.sort() for objects) detects naturally-occurring runs of already-sorted data within the input and merges them directly instead of re-sorting from scratch, so a nearly-sorted array — a common real-world case, like a log file with a few out-of-order entries — sorts in close to linear time instead of n log n. This is a concrete example of why picking an algorithm isn't just about worst-case complexity; real-world input patterns matter.

Why the hash table row has two numbers for everything

A hash table's O(1) average-case performance assumes a well-distributed hash function spreading keys evenly across buckets — but if many keys happen to collide into the same bucket (either through bad luck, a weak hash function, or an attacker deliberately crafting colliding keys — a real denial-of-service technique called hash flooding), lookups in that bucket degrade to a linear scan, which is where the O(n) worst case comes from. This is exactly why the cheat sheet's FAQ calls out that a lower Big-O isn't automatically faster in practice — a binary search tree with a guaranteed O(log n) worst case can genuinely outperform a poorly-hashed hash table under adversarial or unlucky input, even though O(1) looks better on paper.

Why the Space column matters as much as Time

Heapsort and quicksort both run in roughly O(n log n) time, but heapsort does it in O(1) extra space while merge sort needs O(n) extra space for its merge buffers — which is exactly why merge sort is the standard choice for sorting linked lists and external (disk-based) sorts where that auxiliary array is cheap or unnecessary, while heapsort or an in-place quicksort variant is preferred in memory-constrained environments like embedded systems. The lesson generalizes: two algorithms with identical time complexity can have very different real-world suitability once you also weigh their space column, which is why this cheat sheet reports both rather than just picking a single 'best' algorithm per task.

Related tools

More: Developer Tools