# Big O notation cheat sheet – leetcode cheat sheet

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.

What is the Big O notation cheat sheet?

Big O notation cheat sheet summarizes commonly used Big O notations (time complexity and space complexity) in software programming.

What is a leetcode cheat sheet?

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.

### 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 BFSin 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)