5/29/2014 Big-O Algorithm Complexity Cheat Sheet
Know Thy Complexities!
Hi there! This webpage covers the space and time Big-O complexities of common algorithms used in Computer Science. When preparing for
technical interviews in the past, I found myself spending hours crawling the internet putting together the best, average, and worst case
complexities for search and sorting algorithms so that I wouldn't be stumped when asked about them. Over the last few years, I've interviewed
at several Silicon Valley startups, and also some bigger companies, like Yahoo, eBay, LinkedIn, and Google, and each time that I prepared for
an interview, I thought to myself "Why oh why hasn't someone created a nice Big-O cheat sheet?". So, to save all of you fine folks a ton of time,
I went ahead and created one. Enjoy!
Good Fair Poor
Searching
Space
Algorithm Data Structure Time Complexity Complexity
Average Worst Worst
Depth First Search (DFS) Graph of |V| vertices - O(|E| + |V|) O(|V|)
and |E| edges
Breadth First Search Graph of |V| vertices - O(|E| + |V|) O(|V|)
(BFS) and |E| edges
Binary search Sorted array of n O(log(n)) O(log(n)) O(1)
elements
Linear (Brute Force) Array O(n) O(n) O(1)
Shortest path by Dijkstra, Graph with |V| vertices O((|V| + |E|) O((|V| + |E|) O(|V|)
using a Min-heap as and |E| edges log |V|) log |V|)
http://bigocheatsheet.com/# 1/6
5/29/2014 Big-O Algorithm Complexity Cheat Sheet
priority queue
Shortest path by Dijkstra, Graph with |V| vertices O(|V|^2) O(|V|^2) O(|V|)
using an unsorted array and |E| edges
as priority queue
Shortest path by Bellman- Graph with |V| vertices O(|V||E|) O(|V||E|) O(|V|)
Ford and |E| edges
Sorting
Data Worst Case Auxiliary Space
Algorithm Structure Time Complexity Complexity
Best Average Worst Worst
Quicksort Array O(n O(n O(n^2) O(n)
log(n)) log(n))
Mergesort Array O(n O(n O(n O(n)
log(n)) log(n)) log(n))
Heapsort Array O(n O(n O(n O(1)
log(n)) log(n)) log(n))
Bubble Array O(n) O(n^2) O(n^2) O(1)
Sort
Insertion Array O(n) O(n^2) O(n^2) O(1)
Sort
Select Array O(n^2) O(n^2) O(n^2) O(1)
http://bigocheatsheet.com/# 2/6
5/29/2014 Big-O Algorithm Complexity Cheat Sheet
Sort
Bucket Array O(n+k) O(n+k) O(n^2) O(nk)
Sort
Radix Sort Array O(nk) O(nk) O(nk) O(n+k)
Data Structures
Data Space
Structure Time Complexity Complexity
Average Worst Worst
Indexing Search Insertion Deletion Indexing Search Insertion Deletion
Basic O(1) O(n) - - O(1) O(n) - - O(n)
Array
Dynamic O(1) O(n) O(n) O(n) O(1) O(n) O(n) O(n) O(n)
Array
Singly- O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1) O(n)
Linked
List
Doubly- O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1) O(n)
Linked
List
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))
http://bigocheatsheet.com/# 3/6
5/29/2014 Big-O Algorithm Complexity Cheat Sheet
Hash - O(1) O(1) O(1) - O(n) O(n) O(n) O(n)
Table
Binary O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n) O(n) O(n) O(n) O(n)
Search
Tree
Cartresian - O(log(n)) O(log(n)) O(log(n)) - O(n) O(n) O(n) O(n)
Tree
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 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)
Tree
Splay - O(log(n)) O(log(n)) O(log(n)) - O(log(n)) O(log(n)) O(log(n)) O(n)
Tree
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)
Heaps
Heaps Time Complexity
Extract Increase
Heapify Find Max Max Key Insert Delete Merge
Linked - O(1) O(1) O(n) O(n) O(1) O(m+n)
List
(sorted)
Linked - O(n) O(n) O(1) O(1) O(1) O(1)
http://bigocheatsheet.com/# 4/6
5/29/2014 Big-O Algorithm Complexity Cheat Sheet
List
(unsorted)
Binary O(n) O(1) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(m+n)
Heap
Binomial - O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n))
Heap
Fibonacci - O(1) O(log(n))* O(1)* O(1) O(log(n))* O(1)
Heap
Graphs
Node / Edge Storage Add Add Edge Remove Remove Query
Management Vertex Vertex Edge
Adjacency list O(|V|+|E|) O(1) O(1) O(|V| + O(|E|) O(|V|)
|E|)
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| ⋅ O(|V| ⋅ O(|V| ⋅ O(|V| ⋅ O(|V| ⋅ O(|E|)
|E|) |E|) |E|) |E|) |E|)
Notation for asymptotic growth
http://bigocheatsheet.com/# 5/6
5/29/2014 Big-O Algorithm Complexity Cheat Sheet
letter bound growth
(theta) Θ upper and lower, tight[1] equal[2]
(big-oh) O upper, tightness unknown less than or equal[3]
(small-oh) o upper, not tight less than
(big omega) Ω lower, tightness unknown greater than or equal
(small omega) ω lower, not tight greater than
[1] Big O is the upper bound, while Omega is the lower bound. Theta requires both Big O and Omega, so that's why it's referred to as a tight
bound (it must be both the upper and lower bound). For example, an algorithm taking Omega(n log n) takes at least n log n time but has no
upper limit. An algorithm taking Theta(n log n) is far preferential since it takes AT LEAST n log n (Omega n log n) and NO MORE THAN n log n
(Big O n log n).SO
[2] f(x)=Θ(g(n)) means f (the running time of the algorithm) grows exactly like g when n (input size) gets larger. In other words, the growth rate of
f(x) is asymptotically proportional to g(n).
[3] Same thing. Here the growth rate is no faster than g(n). big-oh is the most useful because represents the worst-case behavior.
In short, if algorithm is __ then its performance is __
algorithm performance
o(n) <n
O(n) ≤n
Θ(n) =n
Ω(n) ≥n
ω(n) >n
http://bigocheatsheet.com/# 6/6
