Complexity Cheatsheet

LEGEND

Time &
Space
𝛀 𝚯 O
best avg worst

𝚯 O
average worst
If not in above format assume worst case;
www.mikesollami.com
adjacent duplicates are collapsed:

x x x

Colors
Bad Good

Data Structures Sorting Common Operations

Access Search Insertion Deletion Space Time Complexity Space Time Complexity Space Algorithm

Array 1 n Quicksort n log n 2 log Linear Search 1 n 1

Stack n 1 n Mergesort n log n Binary Search 1 log 1

1.585
Queue n 1 n Int Multiplication n 1 Karatsuba
Timsort n n log 1

2.373
1-Linked List n 1 n Matrix Multiplication n 1 Coppersmith–Winograd
Heapsort n log 1

4
2-Linked List n 1 n 2D Convolution n
Insertion Sort n n 2
1

Skiplist log n n log 3D Convolution n 6

2
Selection Sort n 1
2 2
Hash Table n 2D FFT n log
1 n
2
Tree Sort n log n n
3 3
BST log n n 3D FFT n log

Shell Sort n log n log 2 1

Cartesian Tree n n Graph Walking v+e BFS/DFS
1

Bucket Sort n+k n 2 n

B-Tree log n Max Clique 1.188 n Robson

Radix Sort nk n+k e log v v 2

Red Black Tree log n Shortest Paths v+e Dijkstra

Counting Sort n+k k Min Spanning Tree e log v v 2 v+e Prim

Splay Tree log n

AVL Tree log n Cube Sort n n log n Topological Sort v+e v+e v+e Kahn

KD Tree log n n