Back home

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.

34 topics
TopicOperationAverageWorstSpace
Arrays & VectorsIndex accessO(1)O(1)O(1)
↳SearchO(n)O(n)O(1)
↳Append to vectorO(1) amortizedO(n)O(1)
↳Middle insert/deleteO(n)O(n)O(1)
Strings & ProcessingIndex accessO(1)O(1)O(1)
↳Find substringO(nm)O(nm)O(1)
↳Append characterO(1) amortizedO(n)O(1)
↳Insert/deleteO(n)O(n)O(1)
Singly Linked ListAccess/searchO(n)O(n)O(1)
↳Insert at headO(1)O(1)O(1)
↳Insert at tailO(1)O(n)O(1)
↳Delete after known nodeO(1)O(1)O(1)
Doubly Linked ListSearchO(n)O(n)O(1)
↳Insert at either endO(1)O(1)O(1)
↳Delete known nodeO(1)O(1)O(1)
↳Indexed accessO(n)O(n)O(1)
Circular Linked ListSearchO(n)O(n)O(1)
↳Insert after tailO(1)O(1)O(1)
↳Delete after known nodeO(1)O(1)O(1)
StackspushO(1)O(1)O(1)
↳popO(1)O(1)O(1)
↳topO(1)O(1)O(1)
↳searchO(n)O(n)O(1)
Queues & DequesenqueueO(1)O(1)O(1)
↳dequeueO(1)O(1)O(1)
↳frontO(1)O(1)O(1)
↳searchO(n)O(n)O(1)
Hash TablesSearchO(1)O(n)O(1)
↳InsertO(1)O(n)O(1)
↳DeleteO(1)O(n)O(1)
Linear SearchSearchO(n)O(n)O(1)
Binary SearchSearchO(log n)O(log n)O(1)
Binary Search PatternsBoundary searchO(log n)O(log n)O(1)
↳Answer-space searchO(log range)O(log range)O(1)
Bubble SortSortO(n²)O(n²)O(1)
Selection SortSortO(n²)O(n²)O(1)
Insertion SortSortO(n²)O(n²)O(1)
Shell SortSort≈O(n^1.5)O(n²)O(1)
Merge SortSortO(n log n)O(n log n)O(n)
Quick SortSortO(n log n)O(n²)O(log n)
Counting SortSortO(n+k)O(n+k)O(n+k)
Radix SortSortO(d(n+b))O(d(n+b))O(n+b)
Tree TraversalsTraversalO(n)O(n)O(h)
Binary Search TreeSearchO(log n)O(n)O(1)
↳InsertO(log n)O(n)O(1)
↳DeleteO(log n)O(n)O(1)
AVL TreeSearchO(log n)O(log n)O(1)
↳InsertO(log n)O(log n)O(1)
↳DeleteO(log n)O(log n)O(1)
B-TreeSearchO(log n)O(log n)O(1)
↳InsertO(log n)O(log n)O(1)
↳DeleteO(log n)O(log n)O(1)
Binary HeapPeekO(1)O(1)O(1)
↳InsertO(log n)O(log n)O(1)
↳ExtractO(log n)O(log n)O(1)
↳Build heapO(n)O(n)O(1)
Priority QueuetopO(1)O(1)O(1)
↳pushO(log n)O(log n)O(1)
↳popO(log n)O(log n)O(1)
Heap SortSortO(n log n)O(n log n)O(1)
Graph RepresentationList storageO(V+E)O(V+E)O(V+E)
↳Matrix storageO(V²)O(V²)O(V²)
Breadth-First SearchTraversalO(V+E)O(V+E)O(V)
Depth-First SearchTraversalO(V+E)O(V+E)O(V)
Dijkstra’s AlgorithmShortest pathsO((V+E) log V)O((V+E) log V)O(V+E)
Floyd–WarshallAll-pairs shortest pathsO(V³)O(V³)O(V²)
Disjoint Set Unionfind / unionO(α(n))O(α(n))O(n)
Prim’s MSTMSTO(E log V)O(E log V)O(V+E)
Kruskal’s MSTMSTO(E log E)O(E log E)O(V+E)