# Big O notations and interview questions

Big O notation cheat sheet provides the extended Big O notations for top interview questions. What is Big O notations? Big O notations describe the time or space required for the execution in software program. The execution can be an operation in data structures, such as add, delete or traverse. It can also be an algorithm, such as sort or search. They indicate the worst-case scenario. You can choose the best implementation based on time and space complexity.

In this post, I list the Big O notation cheat sheet for major data structures and well-know algorithms. It also covers some complicated algorithms, such as recursion, DFS and BFS in graph, and memoization in Dynamic programming. The extended Big O notations are the by-product of Java Coding Interview Pocket Book. In this book, every answer for the question includes the Big O notation.

At the end of this post, there is a list of top interview questions aggregated from varied web sites.

### Big O-Notations of 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-Notations of 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)

### Big O-Notations for major Algorithms by categories

 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-Notations of 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-Notations of problems using 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-Notations of problems using 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 Cheat Sheet poster Purchase Big O Notation Cheat Sheet Poster .

### Top interview questions

GeeksforGeeks: Top Data Structure
GeeksforGeeks: Top 10 Algorithms Interview Questions
Javarivisited: Top 30 Programming Questions asked in Interview
Javarevisited: Top 15 Data Structures and Algorithm Interview Questions for Java Programmer
Javarevisited: Top 50 Java Programs from Coding Interviews
LeetCode: Top Interview Questions
ProgramCreek: Top 10 Algorithms for Coding Interview
LaVivienPost: Java Coding Interview Pocket Book (2nd Edition)
LaVivienPost: Java coding interview pocket book insight