Big-O Cheat Sheet


Sorting algorithms are a fundamental part of computer science. Being able to sort through a large data set quickly and efficiently is a problem you will be likely to encounter on nearly a daily basis.

Here are the main sorting algorithms:

AlgorithmData StructureTime Complexity - BestTime Complexity - AverageTime Complexity - WorstWorst Case Auxiliary Space Complexity
QuicksortArrayO(n log(n))O(n log(n))O(n^2)O(n)
Merge SortArrayO(n log(n))O(n log(n))O(n log(n))O(n)
HeapsortArrayO(n log(n))O(n log(n))O(n log(n))O(1)
Bubble SortArrayO(n)O(n^2)O(n^2)O(1)
Insertion SortArrayO(n)O(n^2)O(n^2)O(1)
Select SortArrayO(n^2)O(n^2)O(n^2)O(1)
Bucket SortArrayO(n+k)O(n+k)O(n^2)O(nk)
Radix SortArrayO(nk)O(nk)O(nk)O(n+k)


Another crucial skill to master in the field of computer science is how to search for an item in a collection of data quickly. Here are the most common searching algorithms, their corresponding data structures, and time complexities.

Here are the main searching algorithms:

AlgorithmData StructureTime Complexity - AverageTime Complexity - WorstSpace Complexity - Worst
Depth First SearchGraph of |V| vertices and |E| edges-O(|E|+|V|)O(|V|)
Breadth First SearchGraph of |V| vertices and |E| edges-O(|E|+|V|)O(|V|)
Binary SearchSorted array of n elementsO(log(n))O(log(n))O(1)
Brute ForceArrayO(n)O(n)O(1)
Bellman-FordGraph of |V| vertices and |E| edgesO(|V||E|)O(|V||E|)O(|V|)


Graphs are an integral part of computer science. Mastering them is necessary to become an accomplished software developer. Here is the data structure analysis of graphs:

Node/Edge ManagementStorageAdd VertexAdd EdgeRemove VertexRemove EdgeQuery
Adjacency ListO(|V|+|E|)O(1)O(1)O(|V| + |E|)O(|E|)O(|V|)
Incidence ListO(|V|+|E|)O(1)O(1)O(|E|)O(|E|)O(|E|)
Adjacency MatrixO(|V|^2)O(|V|^2)O(1)O(|V|^2)O(1)O(1)
Incidence MatrixO(|V| ⋅ |E|)O(|V| ⋅ |E|)O(|V| ⋅ |E|)O(|V| ⋅ |E|)O(|V| ⋅ |E|)O(|E|)


Storing information in a way that is quick to retrieve, add, and search on, is a very important technique to master. Here is what you need to know about heap data structures:

HeapsHeapifyFind MaxExtract MaxIncrease KeyInsertDeleteMerge
Sorted Linked List-O(1)O(1)O(n)O(n)O(1)O(m+n)
Unsorted Linked List-O(n)O(n)O(1)O(1)O(1)O(1)
Binary HeapO(n)O(1)O(log(n))O(log(n))O(log(n))O(log(n))O(m+n)
Binomial Heap-O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))
Fibonacci Heap-O(1)O(log(n))*O(1)*O(1)O(log(n))*O(1)