Time-Space-Complexity of algorithms Himanshu Mahuri
SAVE AND SHARE
Topics-
➢ Arrays(time-space-complexity)
➢ Strings(time-space-complexity)
➢ Linked-List(time-space-complexity)
➢ Stack & Queue(time-space-complexity)
➢ Trees(time-space-complexity)
➢ Graph(time-space-complexity)
➢ Heaps(time-space-complexity)
➢ Maps(time-space-complexity)
HIMANSHU MAHURI(LINKEDIN)
https://www.linkedin.com/in/himanshukumarmahuri
pg. 1
Time-Space-Complexity of algorithms Himanshu Mahuri
TIME Worst Case Scenario Average Case Best Case Scenario
COMPLEXITY Scenario
Accessing an O(1) O(1) O(1)
element
Updating an O(1) O(1) O(1)
element
Deleting an O(n) O(n) O(1)
element
Inserting an O(n) O(n) O(1)
element
Searching for O(n) O(n) O(1)
an element
ALGORITHM Time Complexity Space
COMPLEXITY
Complexity
Worst Case Average Case Best Case
Quicksort O(n2) O(n log(n)) O(n log(n)) O(log(n))
Mergesort O(n log(n)) O(n log(n)) O(n log(n)) O(n)
Heapsort O(n log(n)) O(n log(n)) O(n log(n)) O(1)
Bubble Sort O(n2) O(n2) O(n) O(1)
Insertion Sort O(n2) O(n2) O(n) O(1)
Selection Sort O(n2) O(n2) O(n2) O(1)
Binary Search O(log(n)) O(log(n)) O(1) O(1)
Linear Search O(n) O(n) O(1) O(1)
pg. 2
Time-Space-Complexity of algorithms Himanshu Mahuri
TIME Worst Case Average Best Case Scenario
Scenario Case
COMPLEXITY Scenario
Accessing O(1) O(1) O(1)
Deleting O(n) O(n) O(1)
Inserting O(n) O(n) O(1)
Searching O(n * m) O(n) O(1)
(n = string
length m =
pattern length)
Slicing O(n) O(n) O(n)
(n = string length)
Concatenating O(n + m) O(n + m) O(n)
(n, m = string lengths)
Comparison O(n) O(n) O(n)
(n = shorter string
length)
Inserting (Trie) O(m) O(m) O(1)
(m = key
length)
Searching O(m) O(m) O(1)
(Trie)(m = key
length)
ALGORITHM Time Complexity Space
Complexity
COMPLEXITY Worst Case Average Best Case
Case
Radix sort O(n * m) O(n * m) O(n * m) O(n + m)
(m = longest string length)
Naive string O(m*(n-m+1)) O(n * m) O(n) O(1)
search(m = size of
pattern)
Knuth-Morris-Pratt search O(m + n) O(n) O(n) O(m)
Boyer-Moore string O(n * m) O(n) O(n/m) O(m)
search
Rubin-Karp Algorithm O(m*(n-m+1)) O(n + m) O(m) O(m)
pg. 3
Time-Space-Complexity of algorithms Himanshu Mahuri
TIME Worst Case Scenario Average Case Scenario Best Case Scenario
COMPLEXITY
Accessing O(n) O(n) O(1)
Deleting O(1) O(1) O(1)
(after search)
Inserting O(1) O(1) O(1)
(after search)
Searching O(n) O(n) O(1)
Traversing O(n) O(n) O(n)
Access (Skip List) O(n) O(log n) O(log n)
Delete (Skip List) O(n) O(log n) O(log n)
Insert (Skip List) O(n) O(log n) O(log n)
Search (Skip List) O(n) O(log n) O(log n)
ALGORITHM Time Complexity Space Complexity
COMPLEXITY
Worst Case Average Case Best Case
Mergesort O(n log n) O(n log n) O(n log n) O(n)
Bubble Sort O(n²) O(n²) O(n) O(1)
Selection Sort O(n²) O(n²) O(n²) O(1)
Insertion Sort O(n²) O(n²) O(n) O(1)
Linear Search O(n) O(n) O(1) O(1)
pg. 4
Time-Space-Complexity of algorithms Himanshu Mahuri
TIME Worst Case Average Best Case
Scenario Case Scenario
COMPLEXITY Scenario
Delete (Stack) O(1) O(1) O(1)
Insert (Stack) O(1) O(1) O(1)
Search (Stack) O(n) O(n) O(1)
Peek/Top (Stack) O(1) O(1) O(1)
Delete (Queue) O(1) O(1) O(1)
Insert (Queue) O(1) O(1) O(1)
Search (Queue) O(n) O(n) O(1)
ALGORITHM Time Complexity Space
COMPLEXITY
Complexity
Worst Case Average Case Best Case
Linear Search O(n) O(n) O(1) O(1)
pg. 5
Time-Space-Complexity of algorithms Himanshu Mahuri
TIME COMPLEXITY Worst Case Average Case Best Case
Scenario Scenario Scenario
Binary Search Delete O(n) O(log n) O(log n)
Tree,
Cartesian Tree,
KD Tree Insert O(n) O(log n) O(log n)
Search O(n) O(log n) O(log n)
B-Tree, Delete O(log n) O(log n) O(log n)
Red-Black Tree,
Splay Tree,
AVL Tree Insert O(log n) O(log n) O(log n)
Search O(log n) O(log n) O(log n)
Traversal O(n) O(n) O(n)
ALGORITHM Time Complexity Space
Complexity
COMPLEXITY Worst Case Average
Case
Best Case
Depth-First Search O(n) O(n) O(n) O(n)
(In-order, pre-order, and
post-order traversal)
Breadth-First Search O(n) O(n) O(n) O(n)
(Level-order traversal)
Tree Sort O(n2) O(n log n) O(n log n) O(n)
Splaysort O(n log n) O(n log n) O(n) O(n)
Cartesian Tree Sort O(n log n) O(n log n) O(n) O(n)
pg. 6
Time-Space-Complexity of algorithms Himanshu Mahuri
TIME COMPLEXITY Worst Case Average Case Best Case
Scenario Scenario Scenario
Insert Vertex Adjacency List O(1) O(1) O(1)
Adjacency Matrix O(V2) O(V2) O(V2)
Incidence Matrix O(V*E) O(V*E) O(V*E)
Remove Vertex Adjacency List O(E) O(E) O(E)
Adjacency Matrix O(V2) O(V2) O(V2)
Incidence Matrix O(V*E) O(V*E) O(V*E)
Insert Edge Adjacency List O(1) O(1) O(1)
Adjacency Matrix O(1) O(1) O(1)
Incidence Matrix O(V*E) O(V*E) O(V*E)
Remove Edge Adjacency List O(V) O(V) O(V)
Adjacency Matrix O(1) O(1) O(1)
Incidence Matrix O(V*E) O(V*E) O(V*E)
Check if Adjacency List O(V) O(V) O(V)
Vertices
Adjacent Adjacency Matrix O(1) O(1) O(1)
Incidence Matrix O(E) O(E) O(E)
ALGORITHM Time Complexity Space Complexity
COMPLEXITY Worst Case Average Best Case
Case
Breadth-First Search O(V+E) O(V+E) O(V+E) O(V)
Depth-First Search O(V+E) O(V+E) O(V+E) O(V)
A* Search O(E) O(E) O(E) O(V)
Dijkstra’s algorithm O(V2) O(E * log(V)) O(E * log(V)) O(V)
Floyd–Warshall O(V3) O(V3) O(V3) O(V2)
pg. 7
Time-Space-Complexity of algorithms Himanshu Mahuri
TIME Worst Case Average Best Case
Scenario Case Scenario
COMPLEXITY Scenario
Insert O(log n) O(logn) O(1)
Delete O(log n) O(log n) O(1)
Find min/max O(1) O(1) O(1)
Search O(n) O(n) O(1)
Insert O(log n) O(1) O(1)
(Fibonacci/Binomial)
Increase/Decrease O(log n) O(log n) O(1)
key
Extract min/max O(log n) O(log n) O(log n)
ALGORITHM Time Complexity Space
Complexit
COMPLEXITY y
Worst Case Average Best Case
Case
Heapsort O(n log(n)) O(n log(n)) O(n log(n)) O(1)
Smoothsort O(n log(n)) O(n log(n)) O(n) O(n)
Quick select O(n2) O(n) O(n) O(1)
Linear Search O(n) O(n) O(1) O(1)
Dijkstra’s O(V2) O(E * log(V)) O(E * log(V)) O(V)
shortestpath
pg. 8
Time-Space-Complexity of algorithms Himanshu Mahuri
TIME Worst Case Average Best Case Scenario
Scenario Case
COMPLEXITY Scenario
Updating an element O(n) O(1) O(1)
Inserting an element O(n) O(1) O(1)
Deleting an element O(n) O(1) O(1)
Searching for an O(n) O(1) O(1)
element
Insert (TreeMap) O(log n) O(log n) O(1)
Delete (TreeMap) O(log n) O(log n) O(1)
Search (TreeMap) O(log n) O(log n) O(1)
ALGORITHM Time Complexity Space
COMPLEXITY
Complexity
Worst Case Average Case Best Case
Bucket Sort O(n2) O(n + k) O(n + k) O(n)
(k = buckets)
Insertion Sort O(n2) O(n2) O(n) O(1)
Selection Sort O(n2) O(n2) O(n2) O(1)
Heapsort O(n log(n)) O(n log(n)) O(n log(n)) O(1)
Hash-based Search O(n) O(1) O(1) O(1)
Binary Search O(log(n)) O(log(n)) O(1) O(1)
Linear Search O(n) O(n) O(1) O(1)
Rabin-Karp Algorithm O(m*(n-m+1)) O(n + m) O(m) O(m)
pg. 9
