Algorithmic Complexity Cheatsheet
Big O Notation Complexity Chart & Cheatsheet
The complete guide to time and space complexities for core data structures and sorting algorithms.
O(1) Excellent
O(log n) Good
O(n) Fair
O(n log n) Bad
O(n^2) Horrible
Common Data Structure Operations
| Data Structure | Time Complexity (Average) | Time Complexity (Worst) | Space (Worst) | ||||
|---|---|---|---|---|---|---|---|
| Access | Search | Insert | Access | Search | Insert | ||
| Array | O(1) | O(n) | O(n) | O(1) | O(n) | O(n) | O(n) |
| Stack | O(n) | O(n) | O(1) | O(n) | O(n) | O(1) | O(n) |
| Queue | O(n) | O(n) | O(1) | O(n) | O(n) | O(1) | O(n) |
| Singly Linked List | O(n) | O(n) | O(1) | O(n) | O(n) | O(1) | O(n) |
| Hash Table | — | O(1) | O(1) | — | O(n) | O(n) | O(n) |
| Binary Search Tree | O(log n) | O(log n) | O(log n) | O(n) | O(n) | O(n) | O(n) |
| Red-Black / AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
Array Sorting Algorithms
| Algorithm | Best Time | Average Time | Worst Time | Worst Space |
|---|---|---|---|---|
| Quick Sort | O(n log n) | O(n log n) | O(n^2) | O(log n) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) |
| Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) |
| Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) |
Practice Real Coding Interview Problems
Solve Two Sum, Reverse Linked List, Binary Tree Traversal, and classic DSA problems with instant autograded feedback.
Practice DSA Interview Questions