Loading field map
An algorithm is a finite sequence of well-defined instructions, usually intended to be executed by a computer, that takes an input, performs a computation, and produces an output. The study of algorithms is the study of how to solve problems efficiently and correctly. It is not the study of particular programming languages or hardware, but of the underlying logic of computation itself. The field asks a deceptively simple question: given a problem, what is the best way to solve it, and what does "best" even mean?
The central concerns of the discipline are correctness and efficiency. Correctness means that the algorithm always produces the right answer for every valid input. Efficiency is usually measured in terms of time (how many basic operations are performed) and space (how much memory is used). Because computers have finite resources, an algorithm that is correct in principle but takes centuries to finish on a large input is practically useless. The field therefore develops methods for designing algorithms, for proving that they are correct, and for analyzing their resource consumption in a way that is independent of any particular machine.
The concept of an algorithm predates computers by millennia. The term itself derives from the name of the ninth-century Persian mathematician Muhammad ibn Musa al-Khwarizmi, whose work on arithmetic and algebra introduced systematic procedures for solving equations to the Latin-speaking world. However, the modern study of algorithms as a formal discipline began in the twentieth century, driven by two developments: the mathematical formalization of computation and the advent of electronic computers.
In the 1930s, logicians such as Alan Turing and Alonzo Church sought to define precisely what it means for a function to be computable. Turing's abstract machine, now called a Turing machine, provided a simple yet powerful model of computation: an infinite tape, a read-write head, and a finite set of rules. Church's lambda calculus offered an equivalent formalism. Their work established that some problems are simply undecidable—no algorithm can solve them, no matter how much time or memory is available. This was a profound negative result, but it also gave the field a rigorous foundation: an algorithm could now be defined as anything a Turing machine can do.
The practical study of algorithms took off in the 1950s and 1960s as computers became more common. Early programmers discovered that the same problem could be solved in dramatically different ways, with some methods scaling to large inputs while others collapsed. This led to the development of algorithm analysis, the practice of expressing an algorithm's resource usage as a function of the input size. The notation most commonly used, big-O notation, describes the asymptotic growth rate of that function. For example, an algorithm that takes \(O(n^2)\) time on an input of size \(n\) will, for large \(n\), take roughly four times as long when the input doubles, whereas an \(O(n \log n)\) algorithm will grow much more slowly. This abstraction allows comparisons between algorithms that hold across different machines and programming languages.
The field is not organized around rival schools in the way that, say, theoretical physics or philosophy might be. Instead, it is organized around a set of design paradigms—reusable strategies for constructing algorithms—and a set of analysis techniques for evaluating them. These paradigms are not mutually exclusive; many algorithms combine elements of several. Understanding them is the core of the discipline.
One of the oldest and most powerful strategies is divide and conquer. The idea is to break a problem into smaller subproblems, solve each subproblem recursively, and then combine the solutions. The classic example is merge sort: to sort a list, split it in half, sort each half recursively, and then merge the two sorted halves. The algorithm's running time is \(O(n \log n)\), which is provably optimal for comparison-based sorting. Divide and conquer is also the basis for fast multiplication of large numbers, the fast Fourier transform, and many geometric algorithms.
The power of divide and conquer comes from the fact that it often reduces the exponent in the running time. A naive algorithm that examines all pairs of points to find the closest pair in a plane takes \(O(n^2)\) time; a divide-and-conquer approach achieves \(O(n \log n)\). The paradigm also lends itself naturally to analysis via recurrence relations, which express the running time of a recursive algorithm in terms of its running time on smaller inputs. The master theorem provides a general method for solving many such recurrences.
Dynamic programming is a method for solving problems that exhibit optimal substructure (the optimal solution to the whole problem contains optimal solutions to subproblems) and overlapping subproblems (the same subproblem arises many times). Instead of recomputing the solution to a subproblem repeatedly, dynamic programming stores it in a table and looks it up when needed. This trades space for time.
A canonical example is the knapsack problem: given a set of items with weights and values, and a knapsack with a weight limit, choose the subset of items with maximum total value. A naive recursive solution would explore an exponential number of subsets. Dynamic programming solves it in \(O(nW)\) time, where \(n\) is the number of items and \(W\) is the weight limit, by building a table of optimal values for smaller weight limits. Other classic applications include sequence alignment in bioinformatics, shortest paths in graphs, and the computation of edit distances between strings.
Dynamic programming is often contrasted with greedy algorithms, which make the locally optimal choice at each step in the hope of finding a global optimum. Greedy algorithms are faster and simpler, but they only work for problems with a special structure. For example, the greedy algorithm for making change with standard coin denominations (always take the largest coin that fits) works, but it fails for some nonstandard coin sets. Dynamic programming is more general but often requires more time and memory.
A greedy algorithm builds a solution piece by piece, always choosing the option that looks best at the moment, without reconsidering earlier choices. This approach is not always correct, but when it is, it tends to be extremely efficient. The classic success story is Dijkstra's algorithm for finding the shortest path from a source node to all other nodes in a graph with nonnegative edge weights. The algorithm repeatedly selects the unvisited node with the smallest known distance and updates its neighbors. Its running time is \(O((V+E)\log V)\) with a suitable priority queue, where \(V\) is the number of vertices and \(E\) the number of edges.
Another famous greedy algorithm is Huffman coding, used for lossless data compression. It builds a binary tree of character frequencies by repeatedly merging the two least frequent characters, producing a prefix code that minimizes the expected message length. The correctness of greedy algorithms is typically proven by an exchange argument: show that any optimal solution can be transformed into the greedy solution without losing optimality.
Randomized algorithms use random numbers as part of their logic. They come in two flavors. Las Vegas algorithms always produce the correct answer, but their running time is a random variable; Monte Carlo algorithms have a fixed running time but may produce an incorrect answer with a small probability. The most famous randomized algorithm is probably quicksort, which, when it picks a random pivot, runs in expected \(O(n \log n)\) time and in practice is often faster than other sorting algorithms. Randomized algorithms are also used in primality testing (the Miller–Rabin test), hashing, and load balancing.
Randomization is not a way to cheat; it is a way to break worst-case patterns. For many problems, an adversary could construct an input that forces a deterministic algorithm to behave poorly, but if the algorithm makes random choices, no single input can defeat it with certainty. The analysis of randomized algorithms uses probability theory, and the field has developed sophisticated techniques for bounding the probability of failure or the expected running time.
Not all problems can be solved exactly in reasonable time. For NP-hard problems—a class of problems for which no known algorithm runs in polynomial time, and for which it is widely believed that no such algorithm exists—the field turns to approximation algorithms. These are polynomial-time algorithms that produce a solution guaranteed to be within a certain factor of the optimal solution. For example, the traveling salesman problem (find the shortest tour visiting all cities) has a simple approximation algorithm that guarantees a tour at most twice as long as the optimal one, under the triangle inequality. Some problems have polynomial-time approximation schemes, which can get arbitrarily close to optimal at the cost of more time.
When even approximation guarantees are too expensive, practitioners use heuristics: methods that work well in practice but offer no formal guarantee. Examples include simulated annealing, genetic algorithms, and local search. These are not part of the core theory of algorithms, but they are an important practical extension. The boundary between approximation algorithms and heuristics is significant: the former come with mathematical guarantees, the latter do not.
Algorithms do not operate in a vacuum; they require data structures to store and organize information. A data structure is a way of arranging data in memory that supports certain operations efficiently. The choice of data structure is often as important as the choice of algorithm. For example, a hash table supports insertion, deletion, and lookup in expected \(O(1)\) time, making it ideal for dictionaries. A binary search tree supports these operations in \(O(\log n)\) time and also maintains sorted order. A heap supports finding the minimum element in \(O(1)\) time and inserting and deleting in \(O(\log n)\) time, which is why it is used in Dijkstra's algorithm and in priority queues generally.
The study of data structures is tightly coupled with the study of algorithms. Many algorithms are analyzed in terms of the operations they perform on a particular data structure, and the design of new data structures often enables new algorithms. For example, the development of the union-find data structure, which supports efficient merging of sets and queries about set membership, made possible near-linear-time algorithms for computing minimum spanning trees.
A major part of the field is concerned with what cannot be done. Complexity theory classifies problems by the resources required to solve them. The most famous distinction is between P (problems solvable in polynomial time) and NP (problems whose solutions can be verified in polynomial time). The question of whether P equals NP is one of the deepest open problems in mathematics and computer science. It is widely believed that P ≠ NP, meaning that many important problems—such as the traveling salesman problem, Boolean satisfiability, and graph coloring—cannot be solved exactly in polynomial time.
This has profound implications for the practice of algorithms. For NP-hard problems, the field does not seek exact polynomial-time algorithms (because they almost certainly do not exist) but instead seeks approximation algorithms, special cases that are tractable, or algorithms that work well on typical inputs even if they fail on worst-case ones. The theory also includes lower bounds, which prove that any algorithm for a given problem must use at least a certain amount of time or space. For example, any comparison-based sorting algorithm must make at least \(n \log n\) comparisons in the worst case, which is why merge sort is optimal in that model.
The present study of algorithms is shaped by several developments. The rise of massive data has led to the study of external-memory algorithms (which assume data is too large to fit in RAM) and streaming algorithms (which process data in a single pass using limited memory). The growth of parallel and distributed computing has produced algorithms designed for many processors working simultaneously, where the bottleneck is often communication rather than computation. Quantum algorithms, which exploit the principles of quantum mechanics, promise speedups for certain problems, such as Shor's algorithm for factoring integers, though practical quantum computers remain limited.
Machine learning has also influenced the field. Many learning algorithms are optimization algorithms at heart, and the analysis of their convergence and generalization properties borrows from the theory of algorithms. Conversely, the availability of large datasets has made approximate and randomized algorithms more attractive, since exact answers are often unnecessary when data is noisy.
Despite these new directions, the core of the field remains the same as it was decades ago: the design and analysis of correct, efficient procedures. The tools have become more sophisticated, and the problems have become larger and more varied, but the fundamental questions—What is the best way to compute this? How do we know it is correct? How much will it cost?—continue to define the discipline. The study of algorithms is not a collection of tricks but a systematic science of problem-solving, with its own methods of proof, its own notions of optimality, and its own understanding of the boundaries of the computable.