Time and Space Complexity Chart
Algorithm Time Space Where:
Bubble Sort O(n²) O(1) n = elements
Insertion Sort O(n²) O(1) ""
Selection Sort O(n²) O(1) ""
n = elements<br>k = range
Count Sort O(n + k) -> O(n) O(k)
of input, k = 10
Radix Sort<br>(Using n = elements<br>d = digits
O(dn) O(n)
Bucket) (max number)
Radix Sort<br>(Using
O(dn) O(n) ""
Counter)
DFS & BFS (Using List) O(V + E) O(V + E) V = Vertex, Edge
DFS & BFS (Using
O(V²) O(V²) ""
Matrix)
O((V + E) log
Dijkstra O(V + E) ""
V)
Bellman Ford O(V * E) O(V + E) ""
Floyd Warshall O(V³) O(V³) ""
O((V + E) log
Prim's O(V + E) ""
V)
Kruskal's O(E log E) O(V + E) ""
Fibonacci (No DP) O(2^n) O(n) n = nth Fibonacci Number
Fibonacci (DP) O(n) O(n) ""
Important Notes:
Radix Sort Using Counter vs Bucket:
Untitled 1
Radix Sort using Counter (Counting
Feature Radix Sort using Buckets
Sort)
Sorting
Manual bucket distribution Counting Sort (stable version)
subroutine
Stability Must be manually maintained Automatically stable
Speed (in
Slightly slower (due to copying) Faster for large arrays
practice)
Space More memory usage (10 Lower, uses fixed-size count/output
complexity buckets of vectors) arrays
Learning conceptually / Performance matters
Preferred when
visualization (competitive/production)
Adjacency List vs Adjacency Matrix
Situation Best Choice
Sparse Graph (E << V²) Adjacency List
Dense Graph (E ≈ V²) Adjacency Matrix
Need fast edge existence check Adjacency Matrix
Need memory efficiency Adjacency List
Weighted Graph with many nodes Adjacency List
All-pairs shortest path (Floyd-Warshall) Adjacency Matrix
Feature List Matrix
Sparse Graphs ✅ Best ❌ Wasteful
Dense Graphs ⚠️ Ok ✅ Best
Fast edge lookup ❌ (O(degree)) ✅ (O(1))
Space Efficiency ✅ ❌
Weighted Graph ✅ ✅
Operation Adjacency List Adjacency Matrix
Add Edge O(1) O(1)
Remove Edge O(degree) O(1)
Untitled 2
Operation Adjacency List Adjacency Matrix
Check if edge exists O(degree) O(1)
Space O(V + E) O(V²)
Iterate over neighbors O(degree) O(V)
Dijkstra vs Bellman Ford vs Floyd Warshall
Bellman-Ford Floyd-Warshall
Feature Dijkstra’s Algorithm
Algorithm Algorithm
Single Source Single Source All Pairs Shortest
Purpose
Shortest Path (SSSP) Shortest Path (SSSP) Path (APSP)
Only non-negative Can handle negative Can handle negative
Edge Weights
weights weights weights
Negative Cycle
❌ Not supported ✅ Detects negative ✅ Detects negative
Detection cycles cycles
Time Complexity O((V + E) log V) with
O(V × E) O(V³)
(Adj. List) Min Heap
Time Complexity
O(V²) O(V × E) O(V³)
(Adj. Matrix)
Space Complexity O(V + E) O(V + E) O(V²)
Shortest Path Distances from single Distances from Distances between
Output source single source all pairs
Path Via parent[] or prev[] Via parent[] or Via next[][] matrix
Reconstruction array prev[] array (optional)
Fast shortest paths Graphs with Dense graphs, all-
Best Use Case
with non-neg weights negative edges pairs computation
Ease of Complex (Nested
Moderate Easy to Moderate
Implementation loops, Matrix based)
Once per edge Up to V−1 times per Updates every pair
Edge Relaxation
(priority-driven) edge via every node
Prim's vs Kruskal's
Untitled 3
Aspect Prim’s Algorithm Kruskal’s Algorithm
Greedy + Growing a tree from a Greedy + Building MST by
Approach
single node picking edges
Connected, undirected, weighted Connected, undirected, weighted
Works on
graphs graphs
Type of algorithm Greedy Greedy
Starts with an empty forest (no
Starting point Starts with a single node
edges)
Selects the minimum-weight Selects the minimum-weight
Core operation edge from the visited set to an edge that connects two different
unvisited node components
Data structures
Priority queue (Min Heap) Disjoint Set Union (Union-Find)
used
Edge selection From current MST to a new Edge with smallest weight that
criteria vertex with least weight doesn’t form a cycle
Avoids cycles by not revisiting Explicitly checks and avoids
Cycle handling
visited nodes cycles using Union-Find
Graph
Adjacency List / Matrix efficient Edge List preferred
representation
Time Complexity
O((V + E) log V) using Min Heap O(E log E) with efficient DSU
(Optimized)
Space Complexity O(V + E) O(V + E)
Best for Dense graphs (more edges) Sparse graphs (fewer edges)
Doesn’t work on disconnected Can handle disconnected graphs
Edge cases
graphs (gives forest)
Multiple
Components
❌ Not directly (for disconnected ✅ Can form minimum spanning
graphs) forest
Support
Untitled 4