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
- 1Search for a data structure or algorithm.
- 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.