Big O Complexity Cheat Sheet
Interactive algorithm complexity reference covering 28 algorithms across sorting, searching, data structures, and graph algorithms. Filter by category, search by name, and compare best, average, worst, and space complexities. No signup, runs entirely in your browser.
| Algorithm | Best | Average | Worst | Space | Notes |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Stable; rarely used in practice |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | Not stable; minimal swaps |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Stable; fast for small / nearly-sorted arrays |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Stable; consistent performance |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | Not stable; worst case with bad pivots |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | Not stable; in-place |
| Tim Sort | O(n) | O(n log n) | O(n log n) | O(n) | Stable; used in Python/Java |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Stable; k = range of input values |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) | Stable; k = number of digits |
| Linear Search | O(1) | O(n) | O(n) | O(1) | Works on unsorted arrays |
| Binary Search | O(1) | O(log n) | O(log n) | O(1) | Array must be sorted |
| Jump Search | O(1) | O(√n) | O(√n) | O(1) | Sorted arrays; block size √n |
| Interpolation Search | O(1) | O(log log n) | O(n) | O(1) | Uniform distribution assumed |
| Exponential Search | O(1) | O(log n) | O(log n) | O(1) | Unbounded / infinite arrays |
| Array (access) | O(1) | O(1) | O(1) | O(n) | Random access by index |
| Array (search) | O(1) | O(n) | O(n) | O(n) | Unsorted; O(log n) if sorted |
| Array (insert) | O(1) | O(n) | O(n) | O(n) | O(1) at end; O(n) at front/middle |
| Linked List | O(1) | O(n) | O(n) | O(n) | O(1) insert/delete at head |
| Hash Table | O(1) | O(1) | O(n) | O(n) | Worst case with hash collisions |
| BST (balanced) | O(log n) | O(log n) | O(log n) | O(n) | AVL, Red-Black; guaranteed log n |
| BST (unbalanced) | O(log n) | O(log n) | O(n) | O(n) | Degrades to O(n) if skewed |
| Stack / Queue | O(1) | O(1) | O(1) | O(n) | Push, pop, enqueue, dequeue all O(1) |
| Heap (min/max) | O(1) | O(log n) | O(log n) | O(n) | O(1) peek; O(log n) insert/extract |
| BFS | O(V+E) | O(V+E) | O(V+E) | O(V) | V = vertices, E = edges |
| DFS | O(V+E) | O(V+E) | O(V+E) | O(V) | Recursive stack depth = O(V) |
| Dijkstra's | O(E log V) | O(E log V) | O(E log V) | O(V) | Min-heap; non-negative weights |
| Bellman-Ford | O(VE) | O(VE) | O(VE) | O(V) | Handles negative weights |
| Floyd-Warshall | O(V³) | O(V³) | O(V³) | O(V²) | All-pairs shortest path |
| Kruskal's MST | O(E log E) | O(E log E) | O(E log E) | O(V) | Minimum spanning tree; sorts edges |
How to Use Big O Notation
Start with worst case
When comparing algorithms, always check worst-case complexity first. An algorithm that is O(n log n) worst case is safer than one that is O(n log n) average but O(n²) worst case.
Space vs time trade-off
Faster algorithms often use more memory. Merge Sort achieves O(n log n) time but requires O(n) extra space; Heap Sort achieves the same time with O(1) space but is slower in practice due to cache misses.
Constants matter for small n
For small input sizes (n < 50), insertion sort often outperforms Quick Sort despite worse asymptotic complexity because overhead and constants dominate. That is why Timsort uses insertion sort for small runs.
Hash table caveats
Hash map lookups are O(1) average but O(n) worst case due to hash collisions. Most production hash maps handle this with open addressing or chaining, keeping average performance excellent.
Frequently Asked Questions
What is Big O notation?
Big O notation describes how the runtime or memory usage of an algorithm scales with input size n. It expresses the upper bound of growth. O(1) means constant time regardless of input; O(n²) means runtime grows with the square of input size.
What is the difference between best, average, and worst case?
Best case is the fastest the algorithm can run (e.g. a sorted array for insertion sort). Average case is expected performance on typical data. Worst case is the slowest possible scenario and is the most commonly cited for safety-critical comparisons.
What does O(n log n) mean?
O(n log n) means the algorithm performs roughly n × log₂(n) operations. This is the complexity of efficient comparison-based sorting algorithms like Merge Sort and Heap Sort. For n = 1,000,000, that is about 20 million operations instead of 1 trillion for O(n²).
Which sorting algorithm is fastest in practice?
Quick Sort is often fastest in practice despite O(n²) worst case because its cache behavior is excellent and average case is O(n log n). Most standard libraries (Python, Java, etc.) use Timsort, a hybrid of Merge Sort and Insertion Sort.
What is amortized complexity?
Amortized complexity averages the cost of an operation over a sequence of operations. For example, a dynamic array push is O(1) amortized because occasional O(n) resize operations are spread across many O(1) pushes.
Is my data stored when I use this tool?
No. The cheat sheet is entirely static — no data is entered or sent anywhere. It runs fully in your browser.