Mastering Algorithm Design &

Analysis
A comprehensive guide to understanding computational complexity, algorithmic
strategies, and data structure optimization. This presentation covers essential
topics from time complexity analysis to advanced graph algorithms, equipping you
with the theoretical foundations and practical techniques needed to design efficient
solutions for complex computational problems.
Time Complexity Analysis
Asymptotic Notation Common Complexity Classes
Big O (O) - Upper bound representing worst-case complexity.
# O(1) - Constant Time
Describes the maximum time an algorithm could take.
def get_first_element(arr):
"""Accesses an element at a fixed index."""
# Example: Linear Search (Worst Case: item at end or not found)
return arr[0] if arr else None
def linear_search_O(arr, target):
"""
Searches for a target in an array.
Time Complexity: O(n) - In the worst case, we check every # O(log n) - Logarithmic Time
element. def binary_search(arr, target):
""" """Searches a sorted array by repeatedly dividing the search
for i in range(len(arr)): interval in half."""
if arr[i] == target: left, right = 0, len(arr) - 1
return i while left <= right:
return -1 mid = (left + right) // 2
if arr[mid] == target:
# arr = [10, 20, 30, 40, 50], target = 50 (last element) or 60 (not return mid
found) elif arr[mid] < target:
# In both cases, the loop runs 'n' times. left = mid + 1
else:
right = mid - 1
Theta (›) - Tight bound representing average-case complexity. return -1
Describes both upper and lower bounds when they coincide.

# Example: Sum of Array Elements

# O(n) - Linear Time
def sum_array_theta(arr):
def find_max(arr):
""" """Finds the maximum element in an array."""
Calculates the sum of all elements in an array.
if not arr: return None
Time Complexity: ›(n) - We always iterate through all 'n'
max_val = arr[0]
elements,
for x in arr:
regardless of their values. Best, average, and worst cases are all
if x > max_val:
linear. max_val = x
"""
return max_val
total = 0
for num in arr:
total += num
return total # O(n log n) - Linearithmic Time (Merge Sort example)
def merge_sort(arr):
# arr = [1, 2, 3, 4, 5] """Sorts an array using the merge sort algorithm."""
# The loop always runs 'n' times. if len(arr) <= 1:
return arr
mid = len(arr) // 2
Omega («) - Lower bound representing best-case complexity. left_half = arr[:mid]
Describes the minimum time an algorithm requires. right_half = arr[mid:]

left_half = merge_sort(left_half)
# Example: Linear Search (Best Case: item at beginning)
right_half = merge_sort(right_half)
def linear_search_omega(arr, target):
"""
return merge(left_half, right_half)
Searches for a target in an array.
Time Complexity: «(1) - In the best case, the target is the first
def merge(left, right):
element,
"""Merges two sorted arrays."""
and we find it in a single step.
result = []
"""
i=j=0
for i in range(len(arr)):
while i < len(left) and j < len(right):
if arr[i] == target:
if left[i] < right[j]:
return i
[Link](left[i])
return -1
i += 1
else:
# arr = [10, 20, 30, 40, 50], target = 10 (first element)
[Link](right[j])
# The loop runs only once.
j += 1
[Link](left[i:])
[Link](right[j:])
Understanding these notations allows precise communication about
return result
algorithm performance across different input scenarios.

# O(n^2) - Quadratic Time (Bubble Sort example)

def bubble_sort(arr):
"""Sorts an array using the bubble sort algorithm."""
n = len(arr)
for i in range(n - 1): # Outer loop runs n-1 times
for j in range(0, n - i - 1): # Inner loop runs reducing times
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr

# O(2^n) - Exponential Time (Recursive Fibonacci)

def fibonacci_recursive(n):
"""
Calculates the n-th Fibonacci number recursively.
Exhibits exponential time complexity due to redundant
calculations.
"""
if n <= 1:
return n
return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

# O(n!) - Factorial Time (Permutation generation)

from itertools import permutations

def generate_permutations(elements):
"""
Generates all possible permutations of a list of elements.
The number of permutations for 'n' elements is n!.
"""
return list(permutations(elements))

# Example: elements = [1, 2, 3] -> 3! = 6 permutations

O(1) - Constant time: Array access, hash table lookup

O(log n) - Logarithmic: Binary search, balanced tree operations
O(n) - Linear: Single loop iteration, linear search
O(n log n) - Linearithmic: Efficient sorting (merge, heap, quick)
O(n²) - Quadratic: Nested loops, bubble sort
O(2) - Exponential: Recursive subsets, brute force
O(n!) - Factorial: Permutation generation, traveling salesman
brute force

Single Loop Nested Loops Sequential Statements

Time: O(n) Time: O(n²) Time: O(n + m)

def single_loop_example(n): def nested_loops_example(n): def sequential_loops_example(n, m):

""" """ """
This function demonstrates O(n) This function demonstrates O(n^2) This function demonstrates O(n + m)
time complexity. time complexity. time complexity.
The loop runs 'n' times, and each The outer loop runs 'n' times. For The first loop runs 'n' times. The
'operation()' takes constant time. each iteration of the outer loop, second loop runs 'm' times.
Therefore, the total time is directly the inner loop also runs 'n' times. Since they are sequential, their
proportional to 'n'. This results in 'n * n' or 'n^2' total complexities add up.
""" operations. If n dominates m (e.g., n is much
total = 0 """ larger than m), the complexity
for i in range(n): # This loop runs n count = 0 simplifies to O(n).
times for i in range(n): # Outer loop runs n """
total += i # This operation takes times result_n = 0
O(1) time for j in range(n): # Inner loop runs for i in range(n): # This loop runs n
return total n times for EACH outer iteration times
count += 1 # This operation result_n += i
# If n = 5, the loop runs 5 times. If n = takes O(1) time
100, it runs 100 times. return count result_m = 0
# The time taken grows linearly with for j in range(m): # This loop runs m
the input 'n'. # If n = 5, total operations = 25. If n = times
100, total operations = 10,000. result_m += j
# The time taken grows quadratically
Each iteration executes once, resulting in with the input 'n'. return result_n, result_m
linear complexity proportional to input
size. # If n = 1000 and m = 10, the total
Inner loop executes n times for each of n operations are roughly 1000 + 10.
outer iterations, multiplying to quadratic # Asymptotically, we consider the
complexity. largest term, so it's O(max(n, m)).

Independent loops add their complexities.

Dominated by the larger term in
asymptotic analysis.
Sorting Algorithms: Comparison-Based
1 2 3

Bubble Sort Selection Sort Insertion Sort

Time: O(n²) worst/avg, O(n) best | Time: O(n²) all cases | Space: O(1) Time: O(n²) worst/avg, O(n) best |
Space: O(1) Space: O(1)
for i = 0 to n-1:
for i = 0 to n-1: min_idx = i for i = 1 to n:
for j = 0 to n-i-1: for j = i+1 to n: key = arr[i]
if arr[j] > arr[j+1]: if arr[j] < arr[min_idx]: j=i-1
swap(arr[j], arr[j+1]) min_idx = j while j >= 0 and arr[j] > key:
swap(arr[i], arr[min_idx]) arr[j+1] = arr[j]
Repeatedly swaps adjacent elements if j=j-1
out of order. Simple but inefficient for Finds minimum element and places it at arr[j+1] = key
large datasets. the beginning. Performs fewer swaps
than bubble sort. Builds sorted array one element at a time.
Efficient for small or nearly sorted data.

Merge Sort Quick Sort Heap Sort

Time: O(n log n) all cases | Space: O(n) Time: O(n²) worst, O(n log n) avg | Space: Time: O(n log n) all cases | Space: O(1)
O(log n)
MergeSort(arr, l, r): HeapSort(arr):
if l < r: QuickSort(arr, low, high): BuildMaxHeap(arr)
m = (l + r) / 2 if low < high: for i = n-1 to 1:
MergeSort(arr, l, m) pi = Partition(arr, low, high) swap(arr[0], arr[i])
MergeSort(arr, m+1, r) QuickSort(arr, low, pi-1) MaxHeapify(arr, 0, i)
Merge(arr, l, m, r) QuickSort(arr, pi+1, high)
Builds max heap, repeatedly extracts
Divide-and-conquer algorithm that Selects pivot, partitions around it. Lomuto maximum. In-place sorting with
recursively splits array, then merges partition: simpler, pivot at end. Hoare guaranteed O(n log n) performance.
sorted halves. Stable and predictable. partition: more efficient, two-pointer
approach. Randomized: random pivot
avoids worst case.
Linear-Time Sorting & Recurrence Relations
Non-Comparison Sorting Solving Recurrence Relations
Counting Sort - Time: O(n+k), Space: O(k) Substitution Method: Guess solution, prove by induction

CountingSort(arr, k): T(n) = 2T(n/2) + n

count[0...k] = 0 Guess: T(n) = O(n log n)
for i = 0 to n: Prove: T(n) f cn log n
count[arr[i]]++
for i = 1 to k: Recursion Tree: Visualize recursive calls as tree, sum costs
count[i] += count[i-1]
for i = n-1 to 0:
T(n) = 2T(n/2) + n
output[count[arr[i]]-1] = arr[i]
Level 0: n
count[arr[i]]--
Level 1: 2(n/2) = n
...
Counts occurrences of each value. Works when range k is not Height: log n
significantly larger than n. Stable sorting algorithm. Total: n log n

Radix Sort - Time: O(d(n+k)), Space: O(n+k)

Iteration Method: Expand recurrence repeatedly until pattern
emerges
RadixSort(arr):
for digit = LSD to MSD:
CountingSort(arr, digit) T(n) = T(n-1) + n
= T(n-2) + (n-1) + n
= ... = n(n+1)/2
Sorts by individual digits using stable sort. Processes from least to
most significant digit. Efficient for fixed-length integers.
Master Theorem: For T(n) = aT(n/b) + f(n)
Bucket Sort - Time: O(n) avg, O(n²) worst, Space: O(n)
Case 1: If f(n) = O(n^(log_b(a) - ·)), then T(n) = ›(n^log_b(a))

BucketSort(arr): Case 2: If f(n) = ›(n^log_b(a)), then T(n) = ›(n^log_b(a) log n)

Create n empty buckets Case 3: If f(n) = «(n^(log_b(a) + ·)) and regularity holds, then
for i = 0 to n: T(n) = ›(f(n))
Insert arr[i] into bucket[n*arr[i]]
Example: T(n) = 2T(n/2) + n ³ a=2, b=2, f(n)=n ³ Case 2 ³ T(n) =
for each bucket:
›(n log n)
Sort bucket using insertion sort
Concatenate all buckets

Distributes elements into buckets, sorts each bucket. Works well for
uniformly distributed data.
Heaps & Priority Queues

Heap Insertion Heap Deletion Heapify

Time: O(log n) Time: O(log n) Time: O(log n)

Insert(heap, key): ExtractMax(heap): MaxHeapify(heap, i):

[Link]++ max = heap[0] l = 2*i + 1
i = [Link] - 1 heap[0] = heap[[Link]-1] r = 2*i + 2
heap[i] = key [Link]-- largest = i
while i > 0 and heap[parent(i)] < MaxHeapify(heap, 0) if l < size and heap[l] > heap[largest]:
heap[i]: return max largest = l
swap(heap[i], heap[parent(i)]) if r < size and heap[r] > heap[largest]:
i = parent(i) Remove root, replace with last element, largest = r
heapify down to restore property. if largest != i:
Add element at end, bubble up to maintain swap(heap[i], heap[largest])
heap property. Parent at index (i-1)/2. MaxHeapify(heap, largest)

Maintains heap property by comparing with

children, swapping if needed, recursing
down.

Build Heap Priority Queue Operations

Time: O(n) Priority queues efficiently support:

Insert(key): O(log n) - Add element with priority

BuildMaxHeap(arr):
ExtractMax/Min(): O(log n) - Remove highest priority
[Link] = [Link]
for i = n/2 - 1 to 0: GetMax/Min(): O(1) - View highest priority
MaxHeapify(arr, i) IncreaseKey(i, key): O(log n) - Increase priority, bubble up
DecreaseKey(i, key): O(log n) - Decrease priority, bubble down
Surprisingly O(n) not O(n log n)! Start from last non-
Applications: Dijkstra's algorithm, Huffman coding, task scheduling, event
leaf node, heapify each. Most nodes are near bottom
simulation, A* pathfinding, median maintenance.
with small subtrees.

Array Representation
Parent of i: (i-1)/2
Left child of i: 2i+1
Right child of i: 2i+2
Min heap: parent f children
Max heap: parent g children
Greedy Algorithms
Greedy algorithms make locally optimal choices at each step, hoping to find a global optimum. They work when problems exhibit optimal
substructure and the greedy choice property.

Activity Selection Fractional Knapsack Coin Change (Greedy)

Time: O(n log n) Time: O(n log n) Time: O(n)

ActivitySelection(activities): FractionalKnapsack(items, W): CoinChange(coins, amount):

Sort by finish time Sort by value/weight ratio desc Sort coins descending
selected = [activities[0]] total_value = 0 count = 0
last_finish = activities[0].finish for each item: for coin in coins:
for i = 1 to n: if W >= [Link]: count += amount / coin
if activities[i].start >= last_finish: total_value += [Link] amount = amount % coin
[Link](activities[i]) W -= [Link] return count
last_finish = activities[i].finish else:
return selected total_value += [Link] * Minimize coins for change. Works for
(W/[Link]) canonical systems (US coins). May fail for
Select maximum non-overlapping activities. break arbitrary denominations - use DP instead.
Sort by finish time, greedily pick earliest return total_value
finishing compatible activity.
Maximize value in knapsack allowing
fractions. Sort by value density, take items
greedily.

Huffman Coding Traveling Salesman (Greedy Approximation)

Time: O(n log n) Time: O(n²)

HuffmanCoding(frequencies): TSP_Greedy(graph):
Create leaf nodes for each char visited = {start}
Build min heap of nodes current = start
while [Link] > 1: tour = [start]
left = ExtractMin(heap) while [Link] < n:
right = ExtractMin(heap) nearest = FindNearest(current, unvisited)
parent = Node([Link] + [Link]) [Link](nearest)
[Link] = left [Link](nearest)
[Link] = right current = nearest
Insert(heap, parent) [Link](start)
return heap[0] return tour

Optimal prefix-free encoding. Build tree bottom-up by merging two Nearest neighbor heuristic. Not optimal but fast approximation. At
lowest frequency nodes. Left=0, right=1 for encoding. Frequently each city, visit nearest unvisited city. Returns to start.
used characters get shorter codes.
Order Statistics & Dynamic Programming
i-th Order Statistics Dynamic Programming Techniques
Finding the i-th smallest element in an unsorted array. DP solves problems by breaking them into overlapping subproblems, storing
solutions to avoid recomputation.
Max/Min: O(n) - Single pass comparison
Memoization (Top-Down): Recursive with caching
FindMax(arr):
max = arr[0] Fib_Memo(n, memo):
for i = 1 to n: if n in memo: return memo[n]
if arr[i] > max: if n <= 1: return n
max = arr[i] memo[n] = Fib_Memo(n-1, memo) + Fib_Memo(n-2, memo)
return max return memo[n]

Min-Max Pairwise: O(3n/2) - Compare pairs first Tabulation (Bottom-Up): Iterative table filling

FindMinMax(arr): Fib_Tab(n):
Compare pairs, track min/max dp[0] = 0, dp[1] = 1
Comparisons: 3+n/2+ - 2 for i = 2 to n:
dp[i] = dp[i-1] + dp[i-2]
Selection via Sorting: O(n log n) return dp[n]

Select(arr, i):
Sort(arr)
return arr[i]

Randomized Selection (QuickSelect): O(n) avg, O(n²) worst

RandomSelect(arr, l, r, i):
if l == r: return arr[l]
pi = RandomPartition(arr, l, r)
k = pi - l + 1
if i == k: return arr[pi]
else if i < k:
return RandomSelect(arr, l, pi-1, i)
else:
return RandomSelect(arr, pi+1, r, i-k)

Median of Medians: O(n) worst case - Guaranteed linear time

by choosing good pivot

Key DP Properties:

Optimal Substructure: Optimal solution contains optimal solutions to

subproblems
Overlapping Subproblems: Same subproblems solved multiple times
State Definition: What information defines a subproblem
Recurrence Relation: How to compute state from previous states
Base Cases: Smallest subproblems with known solutions
Classic Dynamic Programming Problems

Matrix Chain Multiplication Longest Common Subsequence 0/1 Knapsack

Time: O(n³), Space: O(n²)
(LCS) Time: O(nW), Space: O(nW)
Time: O(mn), Space: O(mn)
MatrixChain(dims): Knapsack(weights, values, W):
for len = 2 to n: LCS(X, Y): for i = 1 to n:
for i = 1 to n-len+1: for i = 1 to m: for w = 0 to W:
j = i + len - 1 for j = 1 to n: if weights[i] <= w:
dp[i][j] = > if X[i] == Y[j]: dp[i][w] = max(dp[i-1][w],
for k = i to j-1: dp[i][j] = dp[i-1][j-1] + 1 values[i] + dp[i-1][w-
cost = dp[i][k] + dp[k+1][j] + else: weights[i]])
dims[i-1]*dims[k]*dims[j] dp[i][j] = max(dp[i-1][j], dp[i] else:
if cost < dp[i][j]: [j-1]) dp[i][w] = dp[i-1][w]
dp[i][j] = cost return dp[m][n]
split[i][j] = k // Reconstruct solution
return dp[1][n] PrintLCS(X, Y, i, j): w=W
if i == 0 or j == 0: return for i = n to 1:
Find optimal parenthesization to if X[i] == Y[j]: if dp[i][w] != dp[i-1][w]:
minimize scalar multiplications. State: PrintLCS(X, Y, i-1, j-1) [Link](i)
dp[i][j] = min cost to multiply matrices i print X[i] w -= weights[i]
to j. else if dp[i-1][j] > dp[i][j-1]: return dp[n][W]
PrintLCS(X, Y, i-1, j)
else: Maximize value without exceeding
PrintLCS(X, Y, i, j-1) weight capacity. Cannot take fractions.
Backtrack to find selected items.
Find longest subsequence common to
both sequences. Backtrack through
table to print actual subsequence.

Optimal BST Coin Change DP Edit Distance

Time: O(n³) Time: O(nV) Time: O(mn)

OptimalBST(keys, freq): CoinChange(coins, V): EditDistance(s1, s2):

for len = 1 to n: dp[0] = 0 for i = 1 to m:
for i = 0 to n-len: for i = 1 to V: for j = 1 to n:
j = i + len - 1 dp[i] = > if s1[i] == s2[j]:
dp[i][j] = > for coin in coins: dp[i][j] = dp[i-1][j-1]
sum = Sum(freq[i..j]) if coin <= i: else:
for r = i to j: dp[i] = min(dp[i], 1 + dp[i- dp[i][j] = 1 + min(
cost = sum + dp[i][r-1] + coin]) dp[i-1][j], // delete
dp[r+1][j] return dp[V] dp[i][j-1], // insert
if cost < dp[i][j]: dp[i-1][j-1]) // replace
dp[i][j] = cost Minimum coins to make value V. Works for
root[i][j] = r any coin system. Minimum operations to transform s1 to s2.
Operations: insert, delete, replace.
Build BST minimizing expected search
cost given key frequencies.
Graph Algorithms: Traversal & Topology
Graph Representations Breadth-First Search (BFS)
Adjacency Matrix: O(V²) space, O(1) edge lookup Time: O(V+E), Space: O(V)

adj[i][j] = 1 if edge exists, 0 otherwise BFS(graph, start):

queue = [start]
Adjacency List: O(V+E) space, O(degree) edge lookup visited[start] = true
distance[start] = 0
while queue not empty:
adj[u] = list of neighbors of u
u = [Link]()
for v in adj[u]:
Graph Types if not visited[v]:
visited[v] = true
Directed: Edges have direction (u³v)
distance[v] = distance[u] + 1
Undirected: Edges bidirectional (u4v)
parent[v] = u
Weighted: Edges have costs/distances [Link](v)
DAG: Directed Acyclic Graph - no cycles
Explores level by level. Finds shortest path in unweighted graphs.
Edge Types (DFS Classification) Tree Diameter: Run BFS from any node to find farthest node, then
Tree Edge: Part of DFS tree BFS from that node.

Back Edge: Points to ancestor (indicates cycle)

Depth-First Search (DFS)
Forward Edge: Points to descendant (not in tree)
Time: O(V+E), Space: O(V)
Cross Edge: Between different subtrees

DFS(graph, u):
visited[u] = true
time++
discovery[u] = time
for v in adj[u]:
if not visited[v]:
parent[v] = u
DFS(graph, v)
time++
finish[u] = time

Explores as deep as possible before backtracking. Used for cycle

detection, topological sort, SCC.

01 02 03

Topological Sort (Kahn's Algorithm) Topological Sort (DFS) Strongly Connected Components
Time: O(V+E) Time: O(V+E)
(Kosaraju)
Time: O(V+E)
TopSort_Kahn(graph): TopSort_DFS(graph):
Compute in-degree for all vertices for each vertex u: Kosaraju(graph):
queue = vertices with in-degree 0 if not visited[u]: // First DFS
while queue not empty: DFS_TopSort(u) for each vertex:
u = [Link]() return reversed(finish_order) if not visited:
[Link](u) DFS(graph, vertex)
for v in adj[u]: DFS_TopSort(u): // Transpose graph
in-degree[v]-- visited[u] = true graph_T = Transpose(graph)
if in-degree[v] == 0: for v in adj[u]: // Second DFS in reverse finish order
[Link](v) if not visited[v]: for vertex in reversed(finish_order):
DFS_TopSort(v) if not visited_T[vertex]:
[Link](u) DFS(graph_T, vertex)
// Each DFS tree is an SCC
Advanced Graph Algorithms & Beyond
Minimum Spanning Tree Shortest Paths Maximum Flow
Kruskal: O(E log E) - Sort edges, use Dijkstra (SSSP): O((V+E) log V) - Ford-Fulkerson/Edmonds-Karp: O(VE²)
Union-Find Non-negative weights
MaxFlow(graph, s, t):
Kruskal(graph): Dijkstra(graph, start): flow = 0
Sort edges by weight dist[start] = 0 while exists augmenting path
MST = [] pq = [(0, start)] (BFS):
for edge (u,v,w) in sorted_edges: while pq not empty: bottleneck = min capacity on
if Find(u) != Find(v): (d, u) = [Link]() path
Union(u, v) for (v, w) in adj[u]: flow += bottleneck
[Link]((u,v,w)) if dist[u] + w < dist[v]: Update residual graph
dist[v] = dist[u] + w return flow
Prim: O(E log V) - Grow tree from start parent[v] = u
vertex [Link]((dist[v], v)) Dinic's Algorithm: O(V²E)

Prim(graph, start): Bellman-Ford (SSSP): O(VE) - Dinic(graph, s, t):

key[start] = 0 Handles negative weights flow = 0
pq = [(0, start)] while BFS builds level graph:
while pq not empty: BellmanFord(graph, start): flow += DFS_blocking_flow()
(w, u) = [Link]() dist[start] = 0 return flow
for (v, weight) in adj[u]: for i = 1 to V-1:
if v not in MST and weight < for each edge (u,v,w): Uses level graphs and blocking flows for
key[v]: if dist[u] + w < dist[v]: better performance.
key[v] = weight dist[v] = dist[u] + w
parent[v] = u // Check negative cycles
[Link]((weight, v)) for each edge (u,v,w):
if dist[u] + w < dist[v]:
return "Negative cycle"

Floyd-Warshall (APSP): O(V³) - All

pairs

FloydWarshall(graph):
for k = 1 to V:
for i = 1 to V:
for j = 1 to V:
dist[i][j] = min(dist[i][j],
dist[i][k] +
dist[k][j])

Cycle Detection Backtracking String Matching

Undirected: DFS with parent tracking N-Queens: Place queens safely KMP: O(n+m)

if visited[v] and v != parent: Solve(row): Build LPS table

cycle exists if row == N: return true Use LPS to skip comparisons
for col in 0 to N:
Directed: DFS with recursion stack if isSafe(row, col): Rabin-Karp: O(n+m) avg
place queen
if Solve(row+1):
if v in rec_stack: Rolling hash comparison
return true
cycle exists Verify on hash match
remove queen

Bipartite Check Union-Find (DSU)

Graph Coloring:

BFS/DFS with 2-coloring Find(x):

Color(v, c):
if neighbor has same color: if parent[x] != x:
if all colored: return true
not bipartite parent[x] = Find(parent[x])
for color in 1 to m:
return parent[x]
if safe:
assign color
Union(x, y):
if Color(v+1, c):
px, py = Find(x), Find(y)
return true
if rank[px] < rank[py]:
unassign
parent[px] = py
else:
parent[py] = px
if rank[px] == rank[py]:
rank[px]++

O(³(n)) per operation with path

compression and union by rank.