Algorithms Tutorial: Learn Problem Solving from Scratch (2026)
Algorithms are the logic that turns raw computational power into purposeful action. After a decade of competitive programming and production system design, I have found that strong algorithmic thinking is what separates engineers who fix symptoms from those who solve root causes. This tutorial covers the essential paradigms — divide and conquer, dynamic programming, greedy methods, and graph algorithms — with an emphasis on recognizing patterns rather than memorizing solutions.
Every algorithm presented here includes a discussion of its correctness proof, complexity analysis, and common implementation pitfalls. We will examine how small changes in problem constraints can shift the optimal approach from a greedy scan to a dynamic programming table spanning thousands of states.
Complexity Analysis and Big-O Notation
Big-O notation describes how an algorithm's runtime grows relative to input size. O(1) denotes constant time, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n^2) quadratic, and O(2^n) exponential. These classifications help us compare algorithms independently of hardware. The art of complexity analysis involves identifying the dominant operation — the inner loop body — and counting how many times it executes. Amortized analysis provides a truer picture for operations that are occasionally expensive but cheap on average, like dynamic array resizing.
# Counting sort O(n + k) where k is the range of input
# Contrast with comparison sorts which are Omega(n log n)
def counting_sort(arr):
if not arr:
return arr
k = max(arr)
counts = [0] * (k + 1)
for x in arr:
counts[x] += 1
i = 0
for val in range(k + 1):
for _ in range(counts[val]):
arr[i] = val
i += 1
return arrDivide and Conquer: Merge Sort and Quick Sort
Divide and conquer splits a problem into independent subproblems, solves each recursively, and combines results. Merge Sort divides the array in half, sorts each half, and merges the sorted halves in O(n) time, yielding O(n log n) worst-case. Quick Sort picks a pivot, partitions elements around it, and recurses on each partition. Its average case is O(n log n) but degrades to O(n^2) with poor pivot selection. Randomizing the pivot or using the median-of-three mitigates this. Both algorithms demonstrate the fundamental trade-off between simplicity and worst-case guarantees.
def quicksort(arr, lo, hi):
if lo < hi:
p = partition(arr, lo, hi)
quicksort(arr, lo, p - 1)
quicksort(arr, p + 1, hi)
def partition(arr, lo, hi):
pivot = arr[hi]
i = lo
for j in range(lo, hi):
if arr[j] <= pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[hi] = arr[hi], arr[i]
return iDynamic Programming: Memoization and Tabulation
Dynamic programming solves problems by breaking them into overlapping subproblems and storing results to avoid redundant work. Memoization is a top-down approach that caches recursive call results, while tabulation builds a bottom-up table. The classic 0/1 knapsack problem illustrates the paradigm: given items with weights and values, maximize the value packed into a capacity-limited knapsack. The recurrence is dp[i][w] = max(dp[i-1][w], dp[i-1][w - wi] + vi). Recognizing that a problem exhibits optimal substructure and overlapping subproblems is the key to applying DP effectively.
def knapsack(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
w, v = weights[i-1], values[i-1]
for c in range(capacity + 1):
if w <= c:
dp[i][c] = max(dp[i-1][c], dp[i-1][c-w] + v)
else:
dp[i][c] = dp[i-1][c]
return dp[n][capacity]Greedy Algorithms
Greedy algorithms make the locally optimal choice at each step, hoping it leads to a globally optimal solution. They work only when the problem exhibits the greedy-choice property — a locally optimal decision is part of some globally optimal solution. Classic examples include Dijkstra's shortest path, Huffman coding, and activity selection. Proving correctness typically involves an exchange argument: show that any optimal solution can be transformed into the greedy one without worsening the objective.
def activity_selection(start, finish):
n = len(start)
activities = sorted(zip(start, finish), key=lambda x: x[1])
selected = [activities[0]]
last_finish = activities[0][1]
for i in range(1, n):
if activities[i][0] >= last_finish:
selected.append(activities[i])
last_finish = activities[i][1]
return selectedGraph Algorithms: Dijkstra and Bellman-Ford
Shortest path algorithms are fundamental to navigation, network routing, and game AI. Dijkstra's algorithm uses a priority queue to repeatedly relax the closest unvisited vertex, achieving O((V+E) log V) with a binary heap. Crucially, it fails on graphs with negative edge weights. Bellman-Ford handles negative weights by relaxing all edges V-1 times, detecting negative cycles on the V-th iteration. This makes it slower at O(VE) but more robust for currency arbitrage detection and constraint satisfaction.
import heapq
def dijkstra(graph, start):
dist = {node: float('inf') for node in graph}
dist[start] = 0
pq = [(0, start)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(pq, (dist[v], v))
return distString Matching: KMP Algorithm
String matching algorithms search for occurrences of a pattern within a text. The naive O(n*m) approach compares the pattern at each position. Knuth-Morris-Pratt (KMP) preprocesses the pattern to build a failure function that indicates how many characters can be skipped when a mismatch occurs. This yields O(n+m) time by avoiding redundant comparisons. The failure function tracks the length of the longest proper prefix that is also a suffix, enabling the algorithm to re-use previously matched information.
def kmp_search(text, pattern):
n, m = len(text), len(pattern)
lps = [0] * m
j = 0
for i in range(1, m):
while j > 0 and pattern[i] != pattern[j]:
j = lps[j-1]
if pattern[i] == pattern[j]:
j += 1
lps[i] = j
j = 0
for i in range(n):
while j > 0 and text[i] != pattern[j]:
j = lps[j-1]
if text[i] == pattern[j]:
j += 1
if j == m:
return i - m + 1
return -1Frequently Asked Questions
How do I choose between recursion and iteration?
Use recursion when the problem naturally maps to a recursive structure (trees, divide-and-conquer) and the recursion depth is bounded by O(log n). Use iteration when stack depth could exceed the call stack limit (usually ~1000 frames) or when performance is critical.
What is the difference between dynamic programming and divide-and-conquer?
Divide-and-conquer splits into independent subproblems (e.g., merge sort). Dynamic programming handles overlapping subproblems where the same subproblem appears multiple times (e.g., Fibonacci, knapsack). DP stores results to avoid recomputation.
When should I use a greedy algorithm instead of DP?
Greedy works when the problem has the greedy-choice property — a local optimum leads to a global optimum. Examples include Huffman coding and Dijkstra's algorithm. If you cannot prove this property, use DP to guarantee optimality.
Why is O(log n) considered efficient?
Logarithmic growth means doubling the input adds only a constant number of operations. Binary search on a sorted array of 1 billion items requires at most 30 comparisons. This scalability makes O(log n) algorithms practical for massive datasets.
Originally published on Ayodhyyya. Last updated June 1, 2026.