Big-O Complexity
Time and space complexity of the data structures and algorithms you use every day.
Growth rates (best → worst)
- O(1)
- Constant — hash lookup, array index
- O(log n)
- Logarithmic — binary search, balanced tree
- O(n)
- Linear — scan a list
- O(n log n)
- Linearithmic — good sorts (merge, heap, quick avg)
- O(n²)
- Quadratic — nested loops, bubble sort
- O(2ⁿ)
- Exponential — subsets, naive recursion
- O(n!)
- Factorial — permutations, brute-force TSP
Data structures (average)
- Array — access
O(1)· searchO(n)· insert/deleteO(n)- Hash map
- search / insert / delete
O(1) - Balanced BST
- search / insert / delete
O(log n) - Heap
- peek
O(1)· push / popO(log n) - Stack / Queue
- push / pop
O(1) - Linked list
- access
O(n)· insert at headO(1)
Sorting
- Quicksort
- avg
O(n log n)· worstO(n²)· in-place - Merge sort
O(n log n)always ·O(n)space · stable- Heap sort
O(n log n)· in-place · not stable- Counting / radix
O(n + k)— non-comparison, bounded keys