An algorithm is a finite, unambiguous sequence of steps that turns input data into a verifiable result. The ten methods in this article are widely known because they express reusable ideas: shrink the search space, divide a problem, traverse a network, retain partial results, or exploit frequencies.
There is no universally best algorithm. A method is effective when it is correct for the available data, meets the time and memory constraints, and guarantees the required result. Pseudocode is intended to explain the idea; real applications should use established, well-tested libraries.
How to read complexity
The notation O(...) describes how cost grows as the input grows; it is not a duration in seconds. In this article n is the number of elements, V the vertices of a graph, E its edges, m the pattern length, W the knapsack capacity, k the number of distinct symbols, and L the message length.
| Order | Practical meaning |
|---|---|
O(1) | Cost does not grow with the input size. |
O(log n) | Each step substantially reduces the problem, often by half. |
O(n) | Work grows in proportion to the elements. |
O(n log n) | Typical cost of efficient general-purpose sorting. |
O(n²) | Cost can rise quickly on large inputs. |
1. Euclidean algorithm
Objective. Compute the greatest common divisor of two integers without listing all their divisors.
Core idea. If a = qb + r, the common divisors of a and b are the same as those of b and the remainder r. Replace the pair with (b, a mod b) until the remainder is zero.
Pseudocode
GCD(a, b)
a ← absolute_value(a)
b ← absolute_value(b)
WHILE b ≠ 0
(a, b) ← (b, a mod b)
RETURN aWorked example. For GCD(252, 105): 252 mod 105 = 42, 105 mod 42 = 21, and 42 mod 21 = 0. The last nonzero remainder is 21.
Complexity. Time O(log min(a,b)) and space O(1) for the iterative version.
When to use it. To reduce fractions, test coprimality, compute periods, and prepare modular-arithmetic operations. The extended version also finds Bézout coefficients and modular inverses.
Important limitation. The case GCD(0,0) must be defined separately because it is indeterminate; the algorithm is not itself a cryptographic system.
2. Binary search
Objective. Find a value in a sorted sequence without inspecting every element.
Core idea. Compare the target with the middle element. The comparison discards the half that cannot contain the answer, and the process continues only in the remaining interval.
Pseudocode
BINARY_SEARCH(A, x)
left ← 0
right ← length(A) − 1
WHILE left ≤ right
middle ← left + floor((right − left) / 2)
IF A[middle] = x RETURN middle
IF A[middle] < x
left ← middle + 1
ELSE
right ← middle − 1
RETURN not_foundWorked example. Search for 23 in [3, 8, 12, 17, 23, 31]. The first middle value is 12, so the left part is discarded; the new middle value is 23 and the search ends.
Complexity. Time O(log n) and space O(1) in the iterative form.
When to use it. On sorted arrays with fast indexed access; also to locate the first or last point at which a monotone property becomes true.
Important limitation. Sorted data is a precondition. If data changes continuously, maintaining order may cost more than the search saves.
3. Merge sort
Objective. Sort a sequence with predictable running time while preserving the relative order of equivalent elements.
Core idea. Split the sequence into two halves, sort each half recursively, and merge them by repeatedly comparing the first elements not yet copied.
Pseudocode
MERGE_SORT(A)
IF length(A) ≤ 1 RETURN A
middle ← floor(length(A) / 2)
left ← MERGE_SORT(A[0 ... middle−1])
right ← MERGE_SORT(A[middle ... end])
RETURN MERGE(left, right)
MERGE(L, R)
result ← empty sequence
WHILE L and R are not empty
move the smaller first element to result
append all remaining elements
RETURN resultWorked example. [8, 3, 5, 1] is split into [8,3] and [5,1]. The halves become [3,8] and [1,5]; merging yields [1,3,5,8].
Complexity. Time O(n log n) in the best, average, and worst cases; typical auxiliary memory O(n). It is stable if the left item is taken first when keys are equal.
When to use it. When predictable performance and stability matter, on linked lists, or for external sorting when the data does not fit in memory.
Important limitation. It needs extra memory for arrays; on very small blocks a simpler sort can have smaller constant costs.
4. Quicksort
Objective. Sort quickly in memory by partitioning the data in place.
Core idea. Choose a pivot, place items no greater than it before it and larger items after it, then recursively sort the two parts. A random pivot lowers the chance of repeatedly unbalanced partitions.
Pseudocode
QUICKSORT(A, low, high)
IF low ≥ high RETURN
p ← RANDOMIZED_PARTITION(A, low, high)
QUICKSORT(A, low, p − 1)
QUICKSORT(A, p + 1, high)
+RANDOMIZED_PARTITION moves a random pivot to its final
+position and returns its indexWorked example. With pivot 5, [8,3,5,1,7] is conceptually partitioned as [3,1] + [5] + [8,7]. Sorting both parts gives [1,3,5,7,8].
Complexity. Expected time O(n log n), worst case O(n²). Partitioning can be in place; expected stack space is O(log n) but can reach O(n).
When to use it. For in-memory arrays when average speed, cache locality, and low auxiliary memory matter. Libraries often use hybrid variants.
Important limitation. It is not normally stable, and consistently poor pivot choices cause quadratic behaviour. In application code, prefer the library sorting function.
5. Breadth-first search (BFS)
Objective. Traverse a graph level by level and find a path with the fewest edges from one source.
Core idea. A queue stores vertices that have been discovered but not explored. Every vertex at distance d is processed before vertices at distance d + 1.
Pseudocode
BFS(G, source)
for every vertex v: visited[v] ← false
visited[source] ← true
distance[source] ← 0
QUEUE.enqueue(source)
WHILE QUEUE is not empty
u ← QUEUE.dequeue()
FOR each v adjacent to u
IF not visited[v]
visited[v] ← true
distance[v] ← distance[u] + 1
parent[v] ← u
QUEUE.enqueue(v)Worked example. If A is joined to B and C, B to D, and C to E, BFS from A visits A first, then B and C, then D and E. The parent array reconstructs one shortest path.
Complexity. With adjacency lists, time O(V+E) and working memory O(V), in addition to the graph.
When to use it. For distances in unweighted graphs, degrees of separation, level-by-level propagation, mazes whose moves all have equal cost, and bipartite testing.
Important limitation. It does not find the least-cost path when edges have different weights; order among vertices at the same level depends on adjacency order.
6. Depth-first search (DFS)
Objective. Explore one branch fully before backtracking to try alternatives.
Core idea. A stack, either explicit or supplied by recursion, stores the current path. When a vertex has no new neighbours, exploration returns to the preceding vertex.
Pseudocode
DFS(G, source)
visited[source] ← true
STACK ← [source]
WHILE STACK is not empty
u ← STACK.pop()
PROCESS(u)
FOR each v adjacent to u
IF not visited[v]
visited[v] ← true
parent[v] ← u
STACK.push(v)Worked example. In the graph A–B, A–C, B–D, and C–E, one possible DFS visits A, B, D, returns to A, and continues with C, E. Another neighbour order gives a different valid traversal.
Complexity. With adjacency lists, time O(V+E) and memory O(V). Very deep recursion can exhaust the language call stack.
When to use it. For connected components, cycle detection, topological sorting of acyclic graphs, maze exploration, and backtracking problems.
Important limitation. It does not guarantee a shortest path. Graph vertices must be marked as visited to prevent infinite cycling.
7. Dijkstra’s algorithm
Objective. Compute shortest distances from one source in a graph with nonnegative edge weights.
Core idea. Maintain a tentative distance for every vertex. A priority queue extracts the closest unsettled vertex; relaxing an edge tests whether reaching its neighbour through that vertex is cheaper.
Pseudocode
DIJKSTRA(G, source)
for every v: distance[v] ← infinity
distance[source] ← 0
PRIORITY_QUEUE.insert(0, source)
WHILE the queue is not empty
(du, u) ← extract_minimum()
IF du ≠ distance[u] CONTINUE
FOR each edge (u, v, weight)
candidate ← du + weight
IF candidate < distance[v]
distance[v] ← candidate
parent[v] ← u
insert(candidate, v)Worked example. With edges A–B:4, A–C:1, C–B:2, B–D:1, and C–D:5, the shortest A-to-D path is A–C–B–D with cost 4.
Complexity. With adjacency lists and a binary heap, time is O((V+E) log V). Distances and parents take O(V); in the simple variant shown, stale heap entries can require up to O(E), in addition to the O(V+E) graph.
When to use it. For road networks without negative costs, routing, weighted dependencies, and any problem reducible to nonnegative weighted shortest paths.
Important limitation. Even one negative edge invalidates the guarantee. Use an algorithm such as Bellman–Ford in that case; when all weights are equal, BFS is sufficient.
8. 0/1 knapsack with dynamic programming
Objective. Choose indivisible items to maximise value without exceeding an integer capacity.
Core idea. Different choices reuse the same subproblems. dp[c] stores the best value possible with capacity c. For each item, capacities are scanned backwards so the same item cannot be selected twice.
Pseudocode
KNAPSACK_01(items, W)
dp[0 ... W] ← 0
FOR each (weight, value) in items
FOR c FROM W DOWN TO weight
dp[c] ← maximum(dp[c], dp[c − weight] + value)
RETURN dp[W]Worked example. With capacity 5 and items (weight 2, value 3), (3,4), and (4,5), the first two fill the knapsack and have value 7, more than any single item.
Complexity. Time O(nW) and memory O(W). This is pseudo-polynomial: it depends on the numeric value of W, not merely on the number of digits used to write it.
When to use it. For moderate integer budgets or capacities, project selection, and resource allocation when each choice may be taken at most once.
Important limitation. With a huge capacity the table is impractical; the simple model also does not represent dependencies between items or non-additive values.
9. Knuth–Morris–Pratt (KMP)
Objective. Find every exact occurrence of a pattern in text without moving backwards through the text.
Core idea. A prefix table records, for each pattern position, the length of the longest prefix that is also a suffix. After a mismatch, that information is reused instead of restarting from zero.
Pseudocode
BUILD_PREFIX_TABLE(P)
prefix[0] ← 0; j ← 0
FOR i FROM 1 TO length(P) − 1
WHILE j > 0 AND P[i] ≠ P[j]
j ← prefix[j − 1]
IF P[i] = P[j] THEN j ← j + 1
prefix[i] ← j
RETURN prefix
KMP(text T, pattern P)
prefix ← BUILD_PREFIX_TABLE(P); j ← 0
FOR i FROM 0 TO length(T) − 1
WHILE j > 0 AND T[i] ≠ P[j]
j ← prefix[j − 1]
IF T[i] = P[j] THEN j ← j + 1
IF j = length(P)
REPORT i − length(P) + 1
j ← prefix[j − 1]Worked example. When searching for ABABAC in ABABABAC, after a mismatch KMP knows that the suffix ABAB is also a useful prefix. It finds the occurrence starting at zero-based index 2.
Complexity. Building the table and searching together take O(n+m); the table uses O(m) memory.
When to use it. For exact search in long texts or streams, especially with highly repetitive patterns and when a linear worst-case guarantee is useful.
Important limitation. It finds exact matches, not approximate ones. The pseudocode assumes a nonempty pattern; for one short search, the language’s optimised built-in search is normally preferable.
10. Huffman coding
Objective. Assign shorter binary codes to frequent symbols and longer codes to rare ones while preserving unique decoding.
Core idea. Insert symbol frequencies into a priority queue and repeatedly combine the two least frequent nodes. Left and right paths in the resulting tree form a prefix code: no code is the prefix of another.
Pseudocode
HUFFMAN(frequencies)
Q ← min_heap with one leaf per symbol
WHILE size(Q) > 1
x ← Q.extract_minimum()
y ← Q.extract_minimum()
z ← node(frequency(x) + frequency(y), x, y)
Q.insert(z)
RETURN Q.extract_minimum()Worked example. For frequencies A:5, B:2, C:1, D:1, one possible code is A=0, B=10, C=110, D=111. The 9 symbols need 15 bits rather than 18 bits with a fixed two-bit code.
Complexity. For k distinct symbols, building the tree costs O(k log k); encoding or decoding a message costs O(L). The tree and table use O(k) space.
When to use it. As a component in compression formats and whenever reliable frequencies are known. It is optimal among prefix codes assigning an integer number of bits to each symbol.
Important limitation. By itself it does not exploit long repetitions or context; for small files, storing the tree can erase the saving. Real data should use standard formats and libraries.
Which algorithm should you choose?
This table does not replace an analysis of the constraints, but it offers a useful starting point.
| Problem | Initial choice | Reason |
|---|---|---|
| Greatest common divisor and coprimality | Euclidean algorithm | It rapidly reduces the pair by using remainders. |
| Value in a sorted sequence | Binary search | It discards half of the interval at each comparison. |
| Stable, predictable sorting | Merge sort | It always guarantees time proportional to n log n. |
| Fast in-memory array sorting | Quicksort | It has excellent average performance and in-place partitioning. |
| Shortest path in an unweighted graph | Breadth-first search (BFS) | Level-order traversal guarantees the fewest edges. |
| Complete exploration, cycles, or backtracking | Depth-first search (DFS) | It follows one branch fully, then returns to alternatives. |
| Shortest path with nonnegative weights | Dijkstra’s algorithm | It always settles the smallest tentative distance. |
| Optimal selection with moderate integer capacity | 0/1 knapsack with dynamic programming | It reuses the results of overlapping subproblems. |
| Exact pattern search in text | Knuth–Morris–Pratt (KMP) | It never rechecks text characters whose information is known. |
| Frequency-based prefix code | Huffman coding | It assigns fewer bits to more frequent symbols. |
Comparing these algorithms reveals a general lesson: first define the input, required result, and constraints precisely; then choose the idea that best exploits the structure of the problem. Correctness and preconditions come before speed.