Big O notation cheat sheet provides the Big O notations for data structures and algorithm, including arrays, linked list, trees, hash tables, graphs, sorting, search, recursion, DFS and BFS, and memoization, Dynamic programming etc. It also includes leetcode Big O cheat sheet for common interview questions. The links are provided to download the jpg file of the cheat sheets. At the end, you can also get the link to download the Big O notation cheat sheet compilation in a poster.
Big O notation cheat sheet summarizes commonly used Big O notations (time complexity and space complexity) in software programming.
The leetcode big O cheat sheet summarizes the Big O notations (time complexity and space complexity) for the leetcode interview questions in data structures and algorithms.
Table of Content
- Big O Notation of Data Structures
- Big O Notation of leetcode Algorithms
- Big O Notation of Sorting Algorithms
- Big O Notation of leetcode questions in Recursions
- Big O Notation of leetcode questions in DFS and BFS
- Big O Notation of Java Collections
- For your consideration
Big O notation – Data Structures
Data structure | Access | Insert | Delete | Search | Traverse |
Linear | |||||
Array | O(1) | O(1) | O(n) | O(n) | O(n) |
Ordered array | O(1) | O(n) | O(n) | O(logn) | O(n) |
Linked list | O(n) | O(1) | O(n) | O(n) | O(n) |
Matrix | O(1) | O(1) | O(1) | O(m*n) | O(m*n) |
Stack | O(1) | O(1) | O(1) | O(n) | O(n) |
Queue | O(1) | O(1) | O(1) | O(n) | O(n) |
Non-linear | |||||
Tree | O(n) | O(1) | O(n) | O(n) | O(n) |
Balanced tree | O(logn) | O(logn) | O(logn) | O(logn) | O(n) |
Graph | O(V) | O(1) | O(V+E) | O(V+E) | O(V+E) |
Trie | O(s) | O(s) | O(s) | O(s) | O(n*s) |
Suffix trie | O(s) | O(s) | O(s) | O(s) | O(s^2) |
Big O notation cheat sheet – leetcode algorithms
Algorithms | Time | Space | Used area |
Sorting | |||
Bubble, Selection, Insertion | O(n^2) | O(1) | Simple sort |
Merge sort | O(n*logn) | O(n) | Stable sort |
Quick sort | O(n*logn) | O(logn) | Quick sort |
Searching | |||
Linear search | O(n) | O(1) | Search in non-sorted array |
Binary search | O(logn) | O(1) | Search in sorted array |
Recursion | |||
Factorial | O(n) | O(n) | Math |
Valid parentheses | O(Cn) | O(Cn) | String |
Permutation | O(n!) | O(n!) | Array, String |
All subsets | O(2^n) | O(2^n) | Array, String |
Dynamic Programming | |||
Fibonacci | O(n) | O(1) | Math |
Knapsack | O(n*w) | O(n*w) | Array |
Edit distance | O(s*t) | O(t) | String |
Num of unique paths in matrix | O(m*n) | O(n) | Matrix |
Big O notation – Sorting Algorithms
Sort | Best | Avg | Worst | Space | Stable |
Bubble sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes |
Selection sort | O(n^2) | O(n^2) | O(n^2) | O(1) | No |
Insertion sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes |
Merge sort | O(n*logn) | O(n*logn) | O(n*logn) | O(n) | Yes |
Quick sort | O(n*logn) | O(n*logn) | O(n^2) | O(logn) | No |
Big O notation cheat sheet – leetcode Recursions
Combinatorics | Sample questions | Formulas | Time |
Permutations | Permutation of array | P(n, k) = n!/(n-k)! | O(P(n,k)), O(n!) when k=n |
Combinations | Combination of range 1..n size k | C(n, k) = n!/(n-k)!k! | O(C(n,k)) |
Combinations of subset | Combination of subset strings | C(m, n) = m^n | O(m^n) |
All subsets | All subset of array | C(2, n)= 2^n | O(2^n) |
Catalan numbers | Generate valid parentheses | Cn = (2n)!/(n+1)!n! | O(Cn) |
Big O notation cheat sheet – leetcode DFS and BFS
DFS and BFS use cases | Sample questions | Time |
DFS in tree | Tree in-order traversal | O(n) |
DFS in string without memo | Word break with recursion | O(2s) |
DFS in string with memo | Word break with rec and memo | O(s2) |
DFS in graph with memo | Graph DFS traversal | O(V+E) |
DFS in matrix with memo | Number of island | O(m*n) |
BFS in tree | Tree level order traversal | O(n) |
BFS/Bi-directional BFS in string with memo | Word ladder with memo | O(s*n) |
BFS in graph with memo | Graph BFS traversal | O(V+E) |
Find path with BFS in graph | Find path from src to dest | O(bd) |
Find path with Bi-directional BFS in graph | Find path with bi-directional BFS | O(bd/2) |
Shortest path with BFS in unweighted and undirected graph | Shortest path from src to dest | O(V+E) |
Shortest path with BFS in adjacent matrix | Shortest path between cells | O(m*n) |
Big O notation – Java Collections
Java
Collections APIs | Access | Insert | Delete | Search | Traverse |
List | |||||
ArrayList | O(1) | O(1) | O(n) | O(n) | O(n) |
LinkedList | O(n) | O(1) | O(n) | O(n) | O(n) |
Stack | O(1) | O(1) | O(1) | O(n) | O(n) |
Queue | |||||
ArrayDeque | O(1) | O(1) | O(1) | O(n) | O(n) |
PriorityQueue | O(logn) | O(logn) | O(logn) | O(logn) | O(n) |
Map | |||||
HashMap | O(1) | O(1) | O(1) | O(1) | O(n) |
LinkedHashMap | O(1) | O(1) | O(1) | O(1) | O(n) |
TreeMap | O(logn) | O(logn) | O(logn) | O(logn) | O(n) |
Dictionary | |||||
Hashtable | O(1) | O(1) | O(1) | O(1) | O(n) |
Set | |||||
HashSet | O(1) | O(1) | O(1) | O(1) | O(n) |
LinkedHashSet | O(1) | O(1) | O(1) | O(1) | O(n) |
TreeSet | O(logn) | O(logn) | O(logn) | O(logn) | O(n) |
