Sorting Concept Time Comparis Stability Space When to

Technique / How it Complexities ons Complex Use / Key

Works (Best / Avg / (Importan ity Points
Worst) t for (Exam
PYQs) Notes)
Linear Check Best: O(1) Worst = n - O(1) Works on
search each Avg: O(n) unsorted
element Worst: O(n) data;
one-by- simplest
one search
Binary Repeated Best: O(1) Worst = - O(1) Requires
Search ly divide Average/Worst log n sorted
sorted = O(n log n) array; very
array fast
into
halves
Insertion Insert Best: O(n) Best: n−1 ✔ Stable O(1) Adaptive,
Sort each (sorted) Worst: good for
element Avg: O(n²) n(n−1)/2 almost-
into Worst: O(n²) sorted
already arrays, used
sorted in small
left part datasets
Selection Repeated Best = Avg = Always ✖ Not O(1) Minimum
Sort ly select Worst = O(n²) n(n−1)/2 stable swaps
minimu (input (n−1), but
m and doesn’t slow, not
swap matter) adaptive
Bubble Swap Best: O(n) with Best: n−1 ✔ Stable O(1) Only good
Sort adjacent flag Worst: when array
if out of Avg/Worst: n(n−1)/2 may be
order; O(n²) nearly
continue sorted
s until no
swaps
Merge Divide Best/ ~ n log n ✔ Stable O(n) Always n
Sort → sort Average/Worst log n, not
halves → = O(n log n) in-place,
merge preferred for
linked lists
Quick Sort Choose Best: O(n log Worst-case ✖ Not O(log n) Fastest in
pivot → n) ~ n(n−1)/2 stable recursion practice, but
partition Avg: O(n log n) worst case
→ Worst: O(n²) occurs if
recurse bad pivot;
randomized
 version
avoids worst
case
Heap Sort Build Best/ Not ✖ Not O(1) In-place,
max Average/Worst commonly stable guaranteed
heap → = O(n log n) counted n log n, used
extract when
max → memory is
heapify limited
Counting Count O(n + k) No ✔ Stable O(k) Use when
Sort occurren compariso (if range k is
ces of ns (non- cumulati small; linear
each key compariso ve) time
n sort)
Radix Sort Sort O(d(n + k)) No ✔ Stable O(n + k) Best for
digit-by- compariso per pass fixed-length
digit ns integers/stri
using ngs; linear
stable time
sort
(usually
counting
sort)
Bucket Distribut Best/Average = No fixed ✔ Stable O(n + k) Works best
Sort e O(n + k) Worst compariso (if stable on uniform
elements = O(n²) n count sub-sort) distribution;
into used for
buckets floats in
→ sort [0,1)
buckets
→ join
Insertion Insert Same as array Same as ✔ Stable O(1) Very
Sort (List into a version array extra efficient for
Form) sorted version linked lists
list compared to
(linked arrays
list)
Merge Same Always O(n log ~ n log n ✔ Stable O(1) Often used
Sort logic, but n) extra for linked
(Linked merging lists because
List) is no extra
pointer- array
based needed
Quick Sort Pivot Expected O(n Same as ✖ Not O(log n) Almost
(Randomiz chosen log n) quick sort stable always used
ed) randoml in practice
 y to avoid
worst-case

Algorithm Concept / Time Compariso Stabili Space When to Use /

/ Topic How it Complexi ns ty Complexi Key Points
Works ty (Best / ty
Avg /
Worst)
BFS Visit nodes O(V + E) — — O(V) Shortest path in
level-by- unweighted
level using a graphs; level
queue order traversal
DFS Go deep first O(V + E) — — O(V) Cycle detection,
using components,
recursion/sta topological
ck sorting
Graph Check if all O(V + E) — — O(V) Find connected
Connectiv nodes are components;
ity reachable check if graph
using is connected
BFS/DFS
Bipartite BFS + O(V + E) — — O(V) Fails if odd
Testing alternate 2- cycle exists;
coloring used in
matching
problems
DAG DFS to O(V + E) — — O(V) Required for
Detection detect back topological
edges (cycle) sort; used in
scheduling
Topologic Order O(V + E) — — O(V) Works only for
al Sorting vertices so DAG; priority
all edges go in dependency
left → right resolution
Prim’s Grow MST O(E log — — O(V) Best for dense
MST from source V) graphs; greedy
using min-
edge
selection
Kruskal’s Sort edges O(E log During — O(V) Best for sparse
MST → pick E) sorting graphs; uses
smallest union-find
edge without
cycle
Fractional Take items O(n log n) Sorting- — O(1) Greedy
Knapsack by highest related optimal; unlike
(Greedy) value/weight 0/1 knapsack
; fractions
allowed
0/1 DP table: O(nW) — — O(nW) Greedy fails;
Knapsack include/excl DP gives
(DP) ude each optimal
item solution
Subset DP table of O(n × — — O(n × Classic DP
Sum (DP) achievable sum) sum) problem; yes/no
sums up to decision
target
Hash Map key → Avg O(1), At collision — O(n) Fast
Table index using Worst search/insert/de
(General) hash O(n) lete
function
Hash Convert key O(1) — — — Good hash
Functions into array prevents
index clustering &
uniformly reduces
collisions
Separate Each index Avg O(1), In linked — O(n) Simple; works
Chaining stores linked Worst list well under high
list of O(n) load factor
collided keys
Linear If slot full → Avg O(1), During — O(1) Causes primary
Probing check next Worst probing clustering; table
sequential O(n) must be <70%
slot full
Quadratic Probe using Avg O(1), — — O(1) Reduces
Probing i² steps Worst primary
O(n) clustering;
secondary
remains
Double Uses second Avg O(1), — — O(1) Best open-
Hashing hash to Worst addressing
compute O(n) method; least
jump size clustering