An algorithm is a precisely specified procedure for carrying out a computation or solving a class of problems. It describes operations that transform permitted inputs into results satisfying a stated requirement. In the classical sense, an algorithm for solving a problem must terminate after finitely many steps on every valid input. Algorithms are central to mathematics and computer science, but they are not necessarily electronic: a person can execute an arithmetic algorithm with pencil and paper. An algorithm is an abstract method, distinct from the particular program or machine implementing it. (xlinux.nist.gov)
Historical development
The word derives from the Latinized name of al-Khwarizmi, the ninth-century mathematician whose work explained calculation using the Hindu–Arabic numeral system. Latin versions of his arithmetic treatise helped transmit these methods to medieval Europe. The related term algorism referred to calculation using these numerals; the modern meaning of algorithm extends beyond arithmetic to general computational procedures. (mathshistory.st-andrews.ac.uk)
Computational procedures predate the word. The Euclidean algorithm, associated with Euclid, calculates the greatest common divisor of two positive integers by repeated division with remainder. The twentieth-century study of algorithms acquired a formal foundation through models of computation. In his paper submitted in 1936, Alan Turing introduced the abstract machine now called a Turing machine, allowing questions about effective computation and its limitations to be expressed mathematically. (xlinux.nist.gov)
Specification and representation
An algorithmic problem specifies valid inputs and acceptable outputs. A sorting problem, for example, requires an output containing exactly the input elements, arranged in a prescribed order. An algorithm supplies a method for obtaining such an output; it must work across the specified input domain, not merely for selected examples. Different algorithms can solve the same problem with different resource requirements. (live.ocw.mit.edu)
Descriptions may use ordinary language, equations, pseudocode, or a programming language. Pseudocode expresses the essential operations without committing to a particular language’s syntax. Algorithms commonly combine sequential instructions, conditional branches, and repeated operations. Recursion expresses a computation through smaller instances of itself, with base cases providing stopping conditions. Data structures specify how information is organized and accessed; their choice can substantially affect efficiency. (xlinux.nist.gov)
For positive integers (a) and (b), the Euclidean algorithm repeatedly replaces ((a,b)) with ((b,a\bmod b)) until (b=0), then returns (a). For example, starting with ((48,18)) gives ((18,12)), ((12,6)), and ((6,0)), so the result is 6. The transformation preserves the common divisors, while each nonzero remainder is smaller than the preceding divisor. These properties explain both correctness and termination. (xlinux.nist.gov)
Correctness and efficiency
Correctness concerns whether an algorithm satisfies its specification. A mathematical proof must establish this for every permitted input. Proofs often use mathematical induction for recursive procedures or a loop invariant—a property maintained throughout repeated execution—for iterative ones. Successful tests provide evidence about particular executions, but do not generally establish correctness over an unrestricted input domain. (live.ocw.mit.edu)
Computational complexity measures resource requirements as input size grows. Time complexity counts operations under a specified computational model; space complexity measures memory usage. Input size may mean the number of records, vertices in a graph, or bits encoding an integer. Consequently, treating arithmetic as a constant-time operation is a modeling assumption rather than a universal fact. (live.ocw.mit.edu)
Big-O notation expresses asymptotic upper bounds, suppressing constant factors and lower-order terms. Binary search locates a value in a sorted array by repeatedly halving the remaining interval, requiring (O(\log n)) comparisons for (n) elements. On a linked list, however, reaching the relevant elements can require linear traversal work. This illustrates why operation counts must be interpreted together with the data representation. (web.stanford.edu)
Worst-case analysis considers the most demanding input of a given size. Average-case analysis assumes a distribution over inputs, whereas expected running time for a randomized algorithm can concern its internal random choices on a fixed input. These are distinct measures and need not produce the same bound. (web.stanford.edu)
Design strategies
Several recurring strategies organize algorithm design:
- Brute force systematically examines candidate solutions.
- Divide and conquer splits a problem into smaller instances, solves them, and combines their results.
- Dynamic programming stores solutions to subproblems so that repeated occurrences need not be recomputed.
- Greedy methods make locally preferred choices. Such choices yield a global optimum only when the problem has suitable structural properties. (live.ocw.mit.edu)
A randomized algorithm incorporates random choices. A Las Vegas algorithm always returns a correct answer, but its running time may vary; a Monte Carlo algorithm may have a controlled probability of returning an incorrect answer. Their analysis uses probability to quantify runtime or error guarantees. Randomization therefore does not simply mean that a procedure is unspecified or unpredictable. (web.stanford.edu)
Limits of algorithmic computation
Not every precisely stated problem admits an algorithmic solution. The halting problem asks whether an arbitrary program, given an input, eventually stops. No algorithm can always answer this question correctly and terminate for every program–input pair. This does not prevent termination from being established for particular programs or restricted classes. Undecidability is different from computational expense: some problems have algorithms whose resource requirements make large instances impractical, while an undecidable problem lacks a general terminating solution altogether. (ocw.mit.edu)