Algorithm Analysis & Design Cheatsheet
Big O Notation
Common Time Complexities
O(1) - Array access, hash table lookup
O(log n) - Binary search, balanced tree operations
O(n) - Linear search, single pass through array
O(n log n) - Merge sort, heap sort, efficient sorting
O(n²) - Bubble sort, selection sort, nested loops
O(2ⁿ) - Recursive fibonacci, subset generation
Multiple Variables Examples
O(|E| + |V|) - BFS, DFS graph traversal
O(|V|²) - Floyd-Warshall all-pairs shortest path
O(|E| log|V|) - Dijkstra with binary heap
O(mn) - 2D grid problems, edit distance
Practical Consequences
n = 10³: O(n²) = 10⁶ ops (~1ms), O(2ⁿ) impossible
n = 10⁶: O(n log n) = 2×10⁷ ops (~20ms), O(n²) = 10¹² ops (hours)
Memory: O(n) = n×8 bytes for integers
Complexity Analysis of Iterative Algorithms
Loop Analysis
for i in range(n): # O(n)
operation()
for i in range(n): # O(n²)
for j in range(n):
operation()
for i in range(n): # O(n log n)
for j in range(i, n, j*2):
operation()
Comparing Algorithms
Insertion Sort: Best O(n), Average/Worst O(n²)
Merge Sort: All cases O(n log n), Space O(n)
Quick Sort: Average O(n log n), Worst O(n²), Space O(log n)
Recurrence Relations
Solving Methods
1. Substitution: Guess solution, prove by induction
2. Recursion Tree: Draw tree, sum levels
3. Master Theorem: Direct formula application
Common Patterns with Examples
T(n) = T(n/2) + O(1) → O(log n) - Binary search
T(n) = T(n/2) + O(n) → O(n) - Randomized select
T(n) = 2T(n/2) + O(n) → O(n log n) - Merge sort
T(n) = 2T(n/2) + O(1) → O(n) - Tree traversal
Master Theorem
Formula: T(n) = aT(n/b) + f(n)
Critical value: n^(log_b(a))
Cases with Examples
1. Case 1: f(n) polynomially smaller
T(n) = 8T(n/2) + n² → a=8, b=2, f(n)=n²
n^(log₂8) = n³ > n², so T(n) = Θ(n³)
2. Case 2: f(n) = Θ(n^(log_b(a)))
T(n) = 2T(n/2) + n → n^(log₂2) = n = f(n)
T(n) = Θ(n log n)
3. Case 3: f(n) polynomially larger + regularity
T(n) = 2T(n/2) + n² → n² > n¹, regularity holds
T(n) = Θ(n²)
Algorithm Design Paradigms
Divide and Conquer
Template:
divide_conquer(problem):
if base_case(problem): return solve_directly(problem)
subproblems = divide(problem)
solutions = [divide_conquer(sub) for sub in subproblems]
return combine(solutions)
Examples:
Merge Sort: T(n) = 2T(n/2) + O(n)
Quick Sort: T(n) = T(k) + T(n-k-1) + O(n)
Closest Pair: T(n) = 2T(n/2) + O(n log n)
Dynamic Programming
1D DP Problems
# Fibonacci
dp[0] = 0, dp[1] = 1
dp[i] = dp[i-1] + dp[i-2]
# Longest Increasing Subsequence
dp[i] = max length ending at position i
dp[i] = max(dp[j] + 1) for all j < i where arr[j] < arr[i]
2D DP Problems
# Edit Distance
dp[i][j] = min edits to transform s1[0:i] to s2[0:j]
if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1]
else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
# Knapsack
dp[i][w] = max value using items 0..i-1 with weight limit w
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])
Backtracking
N-Queens Template:
def solve_nqueens(board, row):
if row == n: return True # All queens placed
for col in range(n):
if is_safe(board, row, col):
board[row][col] = 1
if solve_nqueens(board, row + 1): return True
board[row][col] = 0 # Backtrack
return False
Subset Sum:
def subset_sum(arr, target, index):
if target == 0: return True
if index >= len(arr) or target < 0: return False
return subset_sum(arr, target - arr[index], index + 1) or \
subset_sum(arr, target, index + 1)
Greedy Algorithms
Proof Strategy
1. Greedy Choice Property: Local optimum leads to global optimum
2. Optimal Substructure: Optimal solution contains optimal subsolutions
Examples
# Activity Selection
sort activities by finish time
select activity with earliest finish time that doesn't conflict
# Huffman Coding
while heap has more than 1 node:
merge two nodes with smallest frequency
# Dijkstra's Algorithm
while unvisited vertices exist:
select vertex with minimum distance
update distances to neighbors
Optimization Techniques
Hill Climbing
def hill_climbing(initial_state):
current = initial_state
while True:
neighbors = get_neighbors(current)
best_neighbor = max(neighbors, key=evaluate)
if evaluate(best_neighbor) <= evaluate(current):
return current
current = best_neighbor
Problems: Local optima, plateaus, ridges
Simulated Annealing
def simulated_annealing(initial_state, initial_temp):
current = initial_state
temp = initial_temp
while temp > min_temp:
neighbor = random_neighbor(current)
delta = evaluate(neighbor) - evaluate(current)
if delta > 0 or random() < exp(delta / temp):
current = neighbor
temp *= cooling_rate
return current
Key Parameters:
Initial temperature: High enough to accept bad moves
Cooling schedule: Exponential, linear, or logarithmic
Acceptance probability: P = e^(-ΔE/T)
Problem-Solving Strategy
Step-by-Step Approach
1. Understand constraints: Input size, time limits, memory limits
2. Identify patterns:
Optimization → DP or Greedy
Search space → Backtracking or BFS/DFS
Sorted data → Binary search or two pointers
3. Estimate complexity: Will O(n²) work for n=10⁵?
4. Code and test: Start with brute force, then optimize
Common Complexity Targets
n ≤ 20: O(2ⁿ) or O(n!)
n ≤ 100: O(n³) or O(n² log n)
n ≤ 1000: O(n²)
n ≤ 10⁵: O(n log n)
n ≤ 10⁶: O(n) or O(n log log n)