### Table of Content

- Big O-Notations of Data Structures
- Big O-Notations of Java Collections
- Big O-Notations of Algorithms by categories
- Big O-Notations of Sorting Algorithms
- Big O-Notations of problems using Recursions
- Big O-Notations of problems using DFS and BFS
- Top interview questions

### Introduction

Big O notation interview questions provide the extended Big O notations for top interview questions. What is **Big O notation**? 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. Big O notations include time complexity and space complexity. 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 for major data structures and well-know algorithms. They are also called **Big O notation cheat sheets**. Meanwhile, I extend the basic Big O notations and cover some complicated algorithms, for example, recursion and the graph’s DFS and BFS.

Big O notation interview questions have the exhaustive list of the interview questions, aggregated from varied web sites. This extended Big O notations are the by-product of our Java Coding Interview Pocket Book. In this book, every answer for the question includes the Big O notation.

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

Download data structure cheat sheet

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 |
|||||

Queue |
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) |

Download Java collections cheat sheet

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

Download algorithms cheat sheet

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(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) |

Download recursions cheat sheet

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(2 |

DFS in string with memo |
Word break with rec and memo |
O(s |

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(b |

Find path with Bi-directional BFS in graph |
Find path with bi-directional BFS |
O(b |

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

Download DFS and BFS cheat sheet

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: The complete list of coding interview questions