Big O Cheat Sheet: Time and Space Complexity Table
Best, average and worst-case time complexity and space complexity for 92 algorithms and data structures, from sorting and searching to graphs and dynamic programming. Every row links to a visualizer that runs the algorithm step by step.
Ω is the best case, Θ the average case and O the worst case. For data structures, time is the cost of the main operation (search, insert or delete) and space is the memory the structure holds. New to the notation? Start with Big O notation.
Common complexities, fastest to slowest
| Big O | Name | Typical example |
|---|---|---|
| O(1) | Constant | Array index, hash map lookup, stack push and pop |
| O(log n) | Logarithmic | Binary search, balanced BST operations, heap push and pop |
| O(n) | Linear | One pass over the input: linear search, two pointers, sliding window |
| O(n log n) | Linearithmic | Merge sort, heap sort, sorting before a sweep |
| O(n²) | Quadratic | Nested loops over the input: bubble, insertion and selection sort |
| O(2ⁿ) | Exponential | All subsets: naive recursion, backtracking without pruning |
| O(n!) | Factorial | All orderings: permutations, brute-force travelling salesman |
Mathematics: time and space complexity
All mathematics visualizers| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| GCD / LCM | Ω(1) | Θ(log(min(A, B))) | O(log(min(A, B))) | O(1) |
| Prime Numbers | Ω(1) | Θ(√n) | O(√n) | O(1) |
| Sieve of Eratosthenes | Ω(n log log n) | Θ(n log log n) | O(n log log n) | O(n) |
| Modular Arithmetic | Ω(1) | Θ(1) | O(1) | O(1) |
| Fast Exponentiation | Ω(log B) | Θ(log B) | O(log B) | O(1) |
| Bit Manipulation | Ω(1) | Θ(1) | O(1) | O(1) |
Arrays: time and space complexity
All arrays visualizers| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Array Operations | Ω(1) | Θ(n) | O(n) | O(n) |
| Two Pointers | Ω(1) | Θ(n) | O(n) | O(1) |
| Sliding Window | Ω(n) | Θ(n) | O(n) | O(1) |
| Prefix Sum | Ω(1) | Θ(1) | O(1) | O(n) |
| Kadane's Algorithm | Ω(n) | Θ(n) | O(n) | O(1) |
| Boyer-Moore Voting | Ω(n) | Θ(n) | O(n) | O(1) |
Strings: time and space complexity
All strings visualizers| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Palindrome Check | Ω(1) | Θ(n) | O(n) | O(1) |
| Anagram Check | Ω(1) | Θ(n) | O(n) | O(K) |
| Naive Search | Ω(n) | Θ(n*M) | O(n*M) | O(1) |
| KMP Algorithm | Ω(n + M) | Θ(n + M) | O(n + M) | O(M) |
| Rabin-Karp | Ω(n + M) | Θ(n + M) | O(n*M) | O(1) |
Sorting: time and space complexity
All sorting visualizers| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Bubble Sort | Ω(n) | Θ(n²) | O(n²) | O(1) |
| Selection Sort | Ω(n²) | Θ(n²) | O(n²) | O(1) |
| Insertion Sort | Ω(n) | Θ(n²) | O(n²) | O(1) |
| Merge Sort | Ω(n log n) | Θ(n log n) | O(n log n) | O(n) |
| Quick Sort | Ω(n log n) | Θ(n log n) | O(n²) | O(log n) |
| Heap Sort | Ω(n log n) | Θ(n log n) | O(n log n) | O(1) |
| Shell Sort | Ω(n log n) | Θ(n^1.5) | O(n²) | O(1) |
| Counting Sort | Ω(n + K) | Θ(n + K) | O(n + K) | O(n + K) |
| Radix Sort | Ω(n*k) | Θ(n*k) | O(n*k) | O(n + B) |
| Bucket Sort | Ω(n + k) | Θ(n + k) | O(n²) | O(n + k) |
Searching: time and space complexity
All searching visualizers| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Linear Search | Ω(1) | Θ(n) | O(n) | O(1) |
| Binary Search | Ω(1) | Θ(log n) | O(log n) | O(1) |
Data Structures: time and space complexity
All data structures visualizers| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Stack | Ω(1) | Θ(1) | O(1) | O(n) |
| Queue | Ω(1) | Θ(1) | O(1) | O(n) |
| Deque | Ω(1) | Θ(1) | O(1) | O(n) |
| Circular Queue | Ω(1) | Θ(1) | O(1) | O(n) |
| Priority Queue (ADT) | Ω(1) (Peek) | Θ(log n) (Insert/Delete) | O(log n) (Insert/Delete) | O(n) |
| Tree Traversal | Ω(n) | Θ(n) | O(n) | O(w) or O(h) |
| Binary Tree | Ω(1) | Θ(n) | O(n) | O(n) |
| Binary Search Tree | Ω(log n) | Θ(log n) | O(n) | O(n) |
| AVL Tree | Ω(log n) | Θ(log n) | O(log n) | O(n) |
| Trie (Prefix Tree) | Ω(L) | Θ(L) | O(L) | O(n * L) |
| Segment Tree | Ω(log n) | Θ(log n) | O(log n) | O(n) |
| Fenwick Tree | Ω(log n) | Θ(log n) | O(log n) | O(n) |
| Red-Black Tree | Ω(log n) | Θ(log n) | O(log n) | O(n) |
| Singly Linked List | Ω(1) | Θ(n) | O(n) | O(n) |
| Doubly Linked List | Ω(1) | Θ(n) | O(n) | O(n) |
| Circular Linked List | Ω(1) | Θ(n) | O(n) | O(n) |
| Graph Representation | Ω(1) | Θ(1) | O(V) | O(V + E) |
| Breadth First Search | Ω(V + E) | Θ(V + E) | O(V + E) | O(V) |
| Depth First Search | Ω(V + E) | Θ(V + E) | O(V + E) | O(V) |
| Topological Sort | Ω(V + E) | Θ(V + E) | O(V + E) | O(V + E) |
| Cycle Detection | Ω(V + E) | Θ(V + E) | O(V + E) | O(V) |
| Connected Components | Ω(V + E) | Θ(V + E) | O(V + E) | O(V) |
| Bipartite Graph | Ω(V + E) | Θ(V + E) | O(V + E) | O(V) |
| Dijkstra's Algorithm | Ω(E log V) | Θ(E log V) | O(E log V) | O(V + E) |
| Bellman-Ford Algorithm | Ω(E) | Θ(VE) | O(VE) | O(V) |
| Minimum Spanning Tree | Prim: O(E log V) | Kruskal: O(E log E) | Prim: O(E log V) | Kruskal: O(E log E) | Prim: O(E log V) | Kruskal: O(E log E) | O(V + E) |
| Floyd-Warshall Algorithm | Ω(V³) | Θ(V³) | O(V³) | O(V²) (Matrix) |
| Bridges & Articulation Points | Ω(V + E) | Θ(V + E) | O(V + E) | O(V) (DFS Stack + Arrays) |
Hashing: time and space complexity
All hashing visualizers| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Hash Map | Ω(1) | Θ(1) | O(n) (High Collisions) | O(n) |
| Hash Set | Ω(1) | Θ(1) | O(n) (High Collisions) | O(n) |
| Frequency Table | Ω(n) | Θ(n) | O(n) | O(K) (Unique Elements) |
| Perfect Hashing | Ω(1) | Θ(1) | O(1) | O(n) |
Dynamic Programming: time and space complexity
All dynamic programming visualizers| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Fibonacci Sequence | Ω(n) | Θ(n) | O(n) (vs O(2^n) for naive recursion) | O(n) (Can be optimized to O(1) space) |
| Climbing Stairs | Ω(n) | Θ(n) | O(n) | O(n) (Optimizable to O(1)) |
| Unique Paths | Ω(m*n) | Θ(m*n) | O(m*n) | O(m*n) (Can be optimized to O(n) or O(min(m,n))) |
| 0/1 Knapsack | Ω(n*W) | Θ(n*W) | O(n*W) | O(n*W) (Optimizable to O(W)) |
| Subset Sum | Ω(n*Target) | Θ(n*Target) | O(n*Target) | O(n*Target) (Optimizable to O(Target)) |
| Longest Common Subsequence | Ω(M*n) | Θ(M*n) | O(M*n) | O(M*n) |
| Longest Increasing Subsequence | Ω(n²) | Θ(n²) | O(n²) | O(n) |
| Edit Distance | Ω(M*n) | Θ(M*n) | O(M*n) | O(M*n) |
| Max Path Sum | Ω(n) | Θ(n) | O(n) | O(H) (Recursion Stack) |
| Digit DP | Ω(log n) | Θ(log n * 10) | O(log n * 10 * StateSize) | O(log n) (Recursion Depth) |
Greedy Algorithms: time and space complexity
All greedy algorithms visualizers| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Activity Selection | Ω(n log n) (Sorting) | Θ(n log n) | O(n log n) | O(1) (Auxiliary, excluding sort stack) |
| Huffman Coding | Ω(n log K) (n=len, K=unique chars) | Θ(n log K) | O(n log K) | O(K) (Tree storage) |
| Interval Scheduling | Ω(n log n) (Sorting) | Θ(n log n) | O(n log n) | O(1) (Auxiliary) |
| Job Sequencing | Ω(n log n) | Θ(n log n + n*D) | O(n log n + n*D) | O(D) |
| Minimum Platforms | Ω(n log n) (Sorting) | Θ(n log n) | O(n log n) | O(1) (Auxiliary space for pointers) |
Backtracking: time and space complexity
All backtracking visualizers| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Subsets | Ω(n * 2^n) | Θ(n * 2^n) | O(n * 2^n) | O(n) |
| Permutations | Ω(n * n!) | Θ(n * n!) | O(n * n!) | O(n) (Recursion stack) |
| N-Queens | Ω(n!) | Θ(n!) | O(n!) | O(n) (Recursion stack + board storage) |
| Sudoku Solver | Ω(9^M) (M = empty cells) | Θ(9^M) | O(9^M) | O(M) (recursion stack) |
| Rat in a Maze | Ω(3^(n^2)) | Exponential | O(3^(n^2)) | O(L * n^2) where L is path length |
Advanced Topics: time and space complexity
All advanced topics visualizers| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Heap Operations | Ω(1) (Insert if no swim needed) | Θ(log n) | O(log n) | O(n) |
| Heap Sort | Ω(n log n) | Θ(n log n) | O(n log n) | O(1) |
| Optimized Union-Find | Ω(α(n)) | Θ(α(n)) | O(α(n)) | O(n) |
| Kth Largest Element | Ω(n) | Θ(n log K) | O(n log K) | O(K) |
| Meeting Rooms II | Ω(n log n) | Θ(n log n) | O(n log n) | O(n) |
| Mo's Algorithm | Ω((n+Q) * sqrt(n)) | Θ((n+Q) * sqrt(n)) | O((n+Q) * sqrt(n)) | O(n + Q) |
| Tries | Ω(1) | Θ(L) | O(L) | O(n*L) |
| Z-Algorithm | Ω(n) | Θ(n) | O(n) | O(n) |
| Suffix Array | Ω(n² log n) | Θ(n² log n) | O(n² log n) | O(n) to O(n²) |
| Bitmask DP | Ω(n * 2^n) | Θ(n^2 * 2^n) | O(n^2 * 2^n) | O(n * 2^n) |
| Matrix Exponentiation | Ω(k^3 log n) | Θ(k^3 log n) | O(k^3 log n) | O(k^2) |