Time Complexity By Sahil Sir
Reference for technical interviews
O(1) - Constant
O(log n) - Logarithmic
O(n) - Linear
O(n log n)
O(n²) - Quadratic
O(h) - Height
Array
Access
O(1)
Search
O(n)
Insertion (end)
O(1)
Insertion (middle)
O(n)
Deletion (end)
O(1)
Deletion (middle)
O(n)
String
Access
O(1)
Concatenation
O(n)
Comparison
O(n)
Substring
O(n)
Search (naive)
O(n*m)
Search (KMP)
O(n+m)
Linked List (Singly)
Access
O(n)
Search
O(n)
Insertion (head)
O(1)
Insertion (tail)*
O(1)
Insertion (middle)
O(n)
Deletion (head)
O(1)
Deletion (tail)
O(n)
Doubly Linked List
Access
O(n)
Search
O(n)
Insertion (head/tail)
O(1)
Insertion (middle)
O(n)
Deletion (head/tail)
O(1)
Deletion (middle)
O(n)
Queue (Linked List)
Enqueue
O(1)
Dequeue
O(1)
Peek
O(1)
Search
O(n)
Priority Queue (Heap)
Insert
O(log n)
Extract Min/Max
O(log n)
Peek
O(1)
Search
O(n)
Stack
Push
O(1)
Pop
O(1)
Peek
O(1)
Search
O(n)
Binary Search Tree
Access
O(h)*
Search
O(h)*
Insertion
O(h)*
Deletion
O(h)*
Min/Max
O(h)*
Balanced BST (AVL/RB)
Access
O(log n)
Search
O(log n)
Insertion
O(log n)
Deletion
O(log n)
Min/Max
O(log n)
Time Complexity (Continued)
Reference for technical interviews
Graph (Adjacency List)
Add Vertex
O(1)
Add Edge
O(1)
Remove Vertex
O(|V| + |E|)
Remove Edge
O(|E|)
Query
O(|V|)
BFS/DFS
O(|V| + |E|)
Graph (Adjacency Matrix)
Add Vertex
O(|V|²)
Add Edge
O(1)
Remove Vertex
O(|V|²)
Remove Edge
O(1)
Query
O(1)
BFS/DFS
O(|V|²)
Hash Table
Insert (avg)
O(1)
Insert (worst)
O(n)
Delete (avg)
O(1)
Delete (worst)
O(n)
Search (avg)
O(1)
Search (worst)
O(n)
Map (Hash Based)
Insert (avg)
O(1)
Delete (avg)
O(1)
Search (avg)
O(1)
Worst Case
O(n)
Set (Hash Based)
Insert (avg)
O(1)
Delete (avg)
O(1)
Search (avg)
O(1)
Worst Case
O(n)
TreeSet/TreeMap (Balanced BST)
Insert
O(log n)
Delete
O(log n)
Search
O(log n)
Min/Max
O(log n)
Heap (Binary)
Find Min/Max
O(1)
Extract Min/Max
O(log n)
Insert
O(log n)
Search
O(n)
Decrease Key
O(log n)
Trie
Insert
O(L)
Search
O(L)
Delete
O(L)
Empty Trie
O(1)
L = length of word
Bloom Filter
Insert
O(k)
Search
O(k)
Space
O(m)
k = hash functions
m = bits