Back home34 topics
Complexity reference
Use this page to compare growth rates, then open a topic for its invariants, caveats, and C++ implementation.
Growth-rate ladder
O(1)1/7
Constant
Array indexing, stack top
O(log n)2/7
Logarithmic
Binary search, balanced-tree height
O(n)3/7
Linear
Traversal, linear search
O(n log n)4/7
Linearithmic
Merge sort, average quick sort
O(n²)5/7
Quadratic
Elementary nested-loop sorts
O(2ⁿ)6/7
Exponential
Subset enumeration
O(n!)7/7
Factorial
Permutation enumeration
Operations at a glance
Average and worst cases from every analysed topic.
| Topic | Operation | Average | Worst | Space |
|---|---|---|---|---|
| Arrays & Vectors | Index access | O(1) | O(1) | O(1) |
| ↳ | Search | O(n) | O(n) | O(1) |
| ↳ | Append to vector | O(1) amortized | O(n) | O(1) |
| ↳ | Middle insert/delete | O(n) | O(n) | O(1) |
| Strings & Processing | Index access | O(1) | O(1) | O(1) |
| ↳ | Find substring | O(nm) | O(nm) | O(1) |
| ↳ | Append character | O(1) amortized | O(n) | O(1) |
| ↳ | Insert/delete | O(n) | O(n) | O(1) |
| Singly Linked List | Access/search | O(n) | O(n) | O(1) |
| ↳ | Insert at head | O(1) | O(1) | O(1) |
| ↳ | Insert at tail | O(1) | O(n) | O(1) |
| ↳ | Delete after known node | O(1) | O(1) | O(1) |
| Doubly Linked List | Search | O(n) | O(n) | O(1) |
| ↳ | Insert at either end | O(1) | O(1) | O(1) |
| ↳ | Delete known node | O(1) | O(1) | O(1) |
| ↳ | Indexed access | O(n) | O(n) | O(1) |
| Circular Linked List | Search | O(n) | O(n) | O(1) |
| ↳ | Insert after tail | O(1) | O(1) | O(1) |
| ↳ | Delete after known node | O(1) | O(1) | O(1) |
| Stacks | push | O(1) | O(1) | O(1) |
| ↳ | pop | O(1) | O(1) | O(1) |
| ↳ | top | O(1) | O(1) | O(1) |
| ↳ | search | O(n) | O(n) | O(1) |
| Queues & Deques | enqueue | O(1) | O(1) | O(1) |
| ↳ | dequeue | O(1) | O(1) | O(1) |
| ↳ | front | O(1) | O(1) | O(1) |
| ↳ | search | O(n) | O(n) | O(1) |
| Hash Tables | Search | O(1) | O(n) | O(1) |
| ↳ | Insert | O(1) | O(n) | O(1) |
| ↳ | Delete | O(1) | O(n) | O(1) |
| Linear Search | Search | O(n) | O(n) | O(1) |
| Binary Search | Search | O(log n) | O(log n) | O(1) |
| Binary Search Patterns | Boundary search | O(log n) | O(log n) | O(1) |
| ↳ | Answer-space search | O(log range) | O(log range) | O(1) |
| Bubble Sort | Sort | O(n²) | O(n²) | O(1) |
| Selection Sort | Sort | O(n²) | O(n²) | O(1) |
| Insertion Sort | Sort | O(n²) | O(n²) | O(1) |
| Shell Sort | Sort | ≈O(n^1.5) | O(n²) | O(1) |
| Merge Sort | Sort | O(n log n) | O(n log n) | O(n) |
| Quick Sort | Sort | O(n log n) | O(n²) | O(log n) |
| Counting Sort | Sort | O(n+k) | O(n+k) | O(n+k) |
| Radix Sort | Sort | O(d(n+b)) | O(d(n+b)) | O(n+b) |
| Tree Traversals | Traversal | O(n) | O(n) | O(h) |
| Binary Search Tree | Search | O(log n) | O(n) | O(1) |
| ↳ | Insert | O(log n) | O(n) | O(1) |
| ↳ | Delete | O(log n) | O(n) | O(1) |
| AVL Tree | Search | O(log n) | O(log n) | O(1) |
| ↳ | Insert | O(log n) | O(log n) | O(1) |
| ↳ | Delete | O(log n) | O(log n) | O(1) |
| B-Tree | Search | O(log n) | O(log n) | O(1) |
| ↳ | Insert | O(log n) | O(log n) | O(1) |
| ↳ | Delete | O(log n) | O(log n) | O(1) |
| Binary Heap | Peek | O(1) | O(1) | O(1) |
| ↳ | Insert | O(log n) | O(log n) | O(1) |
| ↳ | Extract | O(log n) | O(log n) | O(1) |
| ↳ | Build heap | O(n) | O(n) | O(1) |
| Priority Queue | top | O(1) | O(1) | O(1) |
| ↳ | push | O(log n) | O(log n) | O(1) |
| ↳ | pop | O(log n) | O(log n) | O(1) |
| Heap Sort | Sort | O(n log n) | O(n log n) | O(1) |
| Graph Representation | List storage | O(V+E) | O(V+E) | O(V+E) |
| ↳ | Matrix storage | O(V²) | O(V²) | O(V²) |
| Breadth-First Search | Traversal | O(V+E) | O(V+E) | O(V) |
| Depth-First Search | Traversal | O(V+E) | O(V+E) | O(V) |
| Dijkstra’s Algorithm | Shortest paths | O((V+E) log V) | O((V+E) log V) | O(V+E) |
| Floyd–Warshall | All-pairs shortest paths | O(V³) | O(V³) | O(V²) |
| Disjoint Set Union | find / union | O(α(n)) | O(α(n)) | O(n) |
| Prim’s MST | MST | O(E log V) | O(E log V) | O(V+E) |
| Kruskal’s MST | MST | O(E log E) | O(E log E) | O(V+E) |