Big-O Reference
Complexity Cheat Sheet
Time and space complexity for all 31 algorithms, filterable by category.
Algorithm | Category | Best | Average | Worst | Space | Tags |
|---|---|---|---|---|---|---|
| Bubble Sort | sorting | O(n²) | O(n²) | O(n²) | O(1) | comparisonin-placestable |
| Selection Sort | sorting | O(n²) | O(n²) | O(n²) | O(1) | comparisonin-placeunstable |
| Insertion Sort | sorting | O(n) | O(n²) | O(n²) | O(1) | comparisonin-placestable |
| Merge Sort | sorting | O(n log n) | O(n log n) | O(n log n) | O(n) | divide-and-conquerstablenot-in-place |
| Quick Sort | sorting | O(n log n) | O(n log n) | O(n²) | O(log n) | divide-and-conquerin-placeunstable |
| Heap Sort | sorting | O(n log n) | O(n log n) | O(n log n) | O(1) | comparisonin-placeunstable |
| Counting Sort | sorting | O(n+k) | O(n+k) | O(n+k) | O(k) | non-comparisonstableinteger-sort |
| Radix Sort | sorting | O(d·n) | O(d·n) | O(d·n) | O(n+k) | non-comparisonstableinteger-sort |
| Shell Sort | sorting | O(n log n) | O(n^1.5) | O(n²) | O(1) | comparisonin-placeunstable |
| Linear Search | searching | O(1) | O(n) | O(n) | O(1) | simpleunsorted |
| Binary Search | searching | O(1) | O(log n) | O(log n) | O(1) | sorteddivide-and-conquerefficient |
| Breadth-First Search | searching | O(V+E) | O(V+E) | O(V+E) | O(V) | graphlevel-ordershortest-path |
| Depth-First Search | searching | O(V+E) | O(V+E) | O(V+E) | O(V) | graphrecursivebacktracking |
| B-Tree | DS | O(log n) | O(log n) | O(log n) | O(n) | treebalancedmultiway |
| B+ Tree | DS | O(log n) | O(log n) | O(log n) | O(n) | treebalancedmultiway |
| B* Tree | DS | O(log n) | O(log n) | O(log n) | O(n) | treebalancedmultiway |
| Extensible Hashing | DS | O(1) | O(1) | O(n) | O(n) | hashdynamicdirectory |
| Array Operations | DS | O(1) | O(n) | O(n) | O(1) | fundamentalrandom-access |
| Singly Linked List | DS | O(1) | O(n) | O(n) | O(n) | dynamicsequentialpointer |
| Doubly Linked List | DS | O(1) | O(n) | O(n) | O(n) | dynamicsequentialpointer |
| Stack | DS | O(1) | O(1) | O(1) | O(n) | LIFOsequentialrecursive |
| Queue | DS | O(1) | O(1) | O(1) | O(n) | FIFOsequentialscheduling |
| Binary Tree Traversals | DS | O(n) | O(n) | O(n) | O(h) | treehierarchicaltraversal |
| Binary Search Tree | DS | O(log n) | O(log n) | O(n) | O(n) | treehierarchicalordered |
| Hash Table | DS | O(1) | O(1) | O(n) | O(n) | hashkey-valueO(1)-lookup |
| Min-Heap | DS | O(1) | O(log n) | O(log n) | O(n) | heappriority-queuecomplete-tree |
| Fibonacci | DP | O(n) | O(n) | O(n) | O(n) | memoizationtabulationoverlapping-subproblems |
| 0/1 Knapsack | DP | O(n·W) | O(n·W) | O(n·W) | O(n·W) | optimizationsubset-selectionclassic |
| Longest Common Subsequence | DP | O(m·n) | O(m·n) | O(m·n) | O(m·n) | stringsubsequencediff |
| Longest Increasing Subsequence | DP | O(n²) | O(n²) | O(n²) | O(n) | subsequencepatience-sortordering |
| Coin Change | DP | O(amount·n) | O(amount·n) | O(amount·n) | O(amount) | optimizationminimum-coinsunbounded |
Big-O Notation Guide
Interactive growth curves, complexity cards, and algorithm examples — all in one place.
Click any algorithm name to open its interactive visualizer.