Big O Time Complexity Cheat Sheet
Every complexity class with real operation counts, and the exact time and space complexity of every algorithm on VizStep — each linked to a step-by-step visualization where you can watch the growth rate happen.
The Complexity Classes
| Class | Name | n = 10 | n = 100 | n = 1,000,000 | Examples |
|---|---|---|---|---|---|
| O(1) | Constant | 1 | 1 | 1 | Hash table lookup, stack push/pop |
| O(log n) | Logarithmic | ~3 | ~7 | ~20 | Binary search, balanced-tree operations |
| O(n) | Linear | 10 | 100 | 1,000,000 | Linear search, array traversal |
| O(n log n) | Linearithmic | ~33 | ~664 | ~2×10⁷ | Merge sort, quicksort (average), heapsort |
| O(n²) | Quadratic | 100 | 10,000 | 10¹² | Bubble/selection/insertion sort, nested loops |
Operation counts are approximate and illustrate growth — the point is the shape, not the exact numbers. At a million elements, the gap between O(n log n) and O(n²) is the gap between ~20 million operations and a trillion.
Every Algorithm on VizStep
| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Stack (LIFO) | O(1) | O(1) | O(1) | O(n) |
| Queue (FIFO) | O(1) | O(1) | O(1) | O(n) |
| Linked List | O(1) | O(n) | O(n) | O(n) |
| Binary Search Tree | O(log n) | O(log n) | O(n) | O(n) |
| AVL Tree | O(log n) | O(log n) | O(log n) | O(n) |
| Min/Max Heap | O(1) | O(log n) | O(log n) | O(n) |
| Hash Table | O(1) | O(1) | O(n) | O(n) |
| BFS (Breadth-First) | O(V+E) | O(V+E) | O(V+E) | O(V) |
| DFS (Depth-First) | O(V+E) | O(V+E) | O(V+E) | O(V) |
| Dijkstra's Algorithm | O(V+E) | O(V²) | O(V²) | O(V) |
| Linear Search | O(1) | O(n) | O(n) | O(1) |
| Binary Search | O(1) | O(log n) | O(log n) | O(1) |
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
Frequently Asked Questions
What does Big O notation actually measure?
Big O describes how an algorithm’s running time (or memory) grows as the input size grows — its growth rate, not its actual speed. Constants and lower-order terms are dropped: an algorithm doing 3n² + 5n + 20 operations is simply O(n²), because for large inputs the n² term dominates everything else.
Is an O(log n) algorithm always faster than an O(n) one?
Not for small inputs. Big O describes growth as n gets large; at n = 10 the constant factors can easily make the "slower" algorithm win. That is why production sorting libraries switch to insertion sort — asymptotically worse — for small subarrays. Asymptotics win eventually, not immediately.
What is the difference between best, average, and worst case?
They describe the same algorithm on different inputs. Quicksort averages O(n log n) on random data but degrades to O(n²) on adversarial input with naive pivots; insertion sort is O(n) on already-sorted data but O(n²) on reversed data. Worst case matters for guarantees, average case for typical performance.
What is the fastest possible comparison-based sort?
O(n log n) is a proven lower bound for comparison-based sorting — no algorithm that only compares elements can beat it in the general case. Sorts that appear faster, like counting sort or radix sort, sidestep the bound by exploiting structure in the keys instead of comparing elements.