Big-O Cheat Sheet – Dhval Mudawal – Rants

View on Evernote.com

Excellent

Good

Fair

Bad

Horrible

Data Structure	Time Complexity								Space Complexity
	Average				Worst				Worst
	Access	Search	Insertion	Deletion	Access	Search	Insertion	Deletion
Array	`O(1)`	`O(n)`	`O(n)`	`O(n)`	`O(1)`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
Stack	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`
Singly-Linked List	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`
Doubly-Linked List	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`
Skip List	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`	`O(n)`	`O(n)`	`O(n)`	`O(n log(n))`
Hash Table	`-`	`O(1)`	`O(1)`	`O(1)`	`-`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
Binary Search Tree	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
Cartesian Tree	`-`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`-`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
B-Tree	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`
Red-Black Tree	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`
Splay Tree	`-`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`-`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`
AVL Tree	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`

Array Sorting Algorithms

Algorithm	Time Complexity			Space Complexity
	Best	Average	Worst	Worst
Quicksort	`O(n log(n))`	`O(n log(n))`	`O(n^2)`	`O(log(n))`
Mergesort	`O(n log(n))`	`O(n log(n))`	`O(n log(n))`	`O(n)`
Timsort	`O(n)`	`O(n log(n))`	`O(n log(n))`	`O(n)`
Heapsort	`O(n log(n))`	`O(n log(n))`	`O(n log(n))`	`O(1)`
Bubble Sort	`O(n)`	`O(n^2)`	`O(n^2)`	`O(1)`
Insertion Sort	`O(n)`	`O(n^2)`	`O(n^2)`	`O(1)`
Selection Sort	`O(n^2)`	`O(n^2)`	`O(n^2)`	`O(1)`
Shell Sort	`O(n)`	`O((nlog(n))^2)`	`O((nlog(n))^2)`	`O(1)`
Bucket Sort	`O(n+k)`	`O(n+k)`	`O(n^2)`	`O(n)`
Radix Sort	`O(nk)`	`O(nk)`	`O(nk)`	`O(n+k)`

Graph Operations

Node / Edge Management	Storage	Add Vertex	Add Edge	Remove Vertex	Remove Edge	Query
Adjacency list	`O(\|V\|+\|E\|)`	`O(1)`	`O(1)`	`O(\|V\| + \|E\|)`	`O(\|E\|)`	`O(\|V\|)`
Incidence list	`O(\|V\|+\|E\|)`	`O(1)`	`O(1)`	`O(\|E\|)`	`O(\|E\|)`	`O(\|E\|)`
Adjacency matrix	`O(\|V\|^2)`	`O(\|V\|^2)`	`O(1)`	`O(\|V\|^2)`	`O(1)`	`O(1)`
Incidence matrix	`O(\|V\| ⋅ \|E\|)`	`O(\|V\| ⋅ \|E\|)`	`O(\|V\| ⋅ \|E\|)`	`O(\|V\| ⋅ \|E\|)`	`O(\|V\| ⋅ \|E\|)`	`O(\|E\|)`

Heap Operations

Type	Time Complexity
	Heapify	Find Max	Extract Max	Increase Key	Insert	Delete	Merge
Linked List (sorted)	`-`	`O(1)`	`O(1)`	`O(n)`	`O(n)`	`O(1)`	`O(m+n)`
Linked List (unsorted)	`-`	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(1)`	`O(1)`
Binary Heap	`O(n)`	`O(1)`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(m+n)`
Binomial Heap	`-`	`O(1)`	`O(log(n))`	`O(log(n))`	`O(1)`	`O(log(n))`	`O(log(n))`
Fibonacci Heap	`-`	`O(1)`	`O(log(n))`	`O(1)`	`O(1)`	`O(log(n))`	`O(1)`

Recommended Reading