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.

Table of Content


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

Download sorting cheat sheet


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

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: Java Coding Interview Pocket Book (2nd Edition)
LaVivienPost: Java coding interview pocket book insight

Comments are closed