Most Influential Algorithms of All Time

Below is a ranked list of algorithms that have had the greatest influence in computer science, judged by their historical significance, efficiency, real-world applications, and academic impact. Each entry includes a brief description of the algorithm’s key contributions, complexity, and uses, with references to seminal papers or implementations.

1. Quicksort (Sorting) – Quicksort is a divide-and-conquer sorting algorithm developed by C.A.R. Hoare (1960) that recursively partitions arrays around a pivot. On average it runs in O(n log n) time​ (with a worst-case of O(n²) mitigated by randomized pivots) and sorts in-place using minimal extra memory. Quicksort’s combination of speed and low memory footprint made it the default sorting method in many libraries (e.g. Unix qsort and Java’s sort)​. Its efficiency and elegance have made it historically significant, inspiring a generation of optimized sorting techniques and cementing its use in systems ranging from databases to operating systems.

2. RSA (Public-Key Cryptography) – RSA, introduced by Rivest, Shamir, and Adleman in 1977, revolutionized security by enabling public-key encryption. It relies on the mathematical difficulty of factoring large integers: data encrypted with a public key can only be decrypted with the corresponding private key​. RSA brought secure communications to the internet age – it underpins protocols like TLS/SSL (HTTPS), secure email, and digital signatures​. This algorithm’s impact is enormous: it provided a practical method for secure key exchange and digital identity, and its longevity in real-world use showcases its design strength (though a sufficiently large quantum computer running Shor’s algorithm could threaten it in the future​).

3. Backpropagation (Neural Network Training) – Backpropagation (1986) is the algorithm that made training deep neural networks feasible by efficiently computing error gradients for multilayer networks​. Using the chain rule of calculus, it propagates the output error backward through each layer to adjust weights via gradient descent. This ability to “learn” internal representations from data was the key to the late-20th-century resurgence of neural networks​. Backpropagation is computationally efficient (scaling linearly with the number of connections) and, coupled with improvements in computing power, led to today’s deep learning revolution. It is the foundation of training algorithms in computer vision, speech recognition, and NLP – virtually all modern deep learning models “learn by back-propagating errors”​, making backprop one of the most influential algorithms in AI history.

4. Dijkstra’s Algorithm (Shortest Paths in Graphs) – Dijkstra’s algorithm (1956) finds the shortest path from a source node to all other nodes in a weighted graph with non-negative edge weights​. It systematically “relaxes” distances via a greedy strategy, using a priority queue for efficiency, to achieve a run-time of O(V²) (or O((V+E) log V) with a min-heap)​. This classic algorithm introduced optimal graph search techniques and is widely used in network routing and mapping applications – for example, in Internet routing protocols like OSPF it computes best paths​. Dijkstra’s method also laid the groundwork for many extensions; it’s essentially a uniform-cost search that A* later augmented with heuristics​. Its combination of elegance and practicality has made it a staple in algorithm textbooks and real-world systems (like GPS navigation systems finding quickest routes).

5. PageRank (Web Page Ranking) – PageRank (1998) is the algorithm that originally powered Google’s search engine, transforming how information is found on the web. Developed by Larry Page and Sergey Brin, PageRank models the web as a directed graph and uses link analysis to rank pages by their “importance.” In simplified terms, a page’s rank increases if many other high-ranked pages link to it​. This approach, based on iterative eigenvector computation, yielded far more relevant search results than earlier keyword-based ranking​. PageRank’s ability to handle the scale and authority structure of the web was historically significant – it turned Google into the world’s dominant search engine and influenced virtually all modern search ranking algorithms. Today, pure PageRank is augmented by many other factors, but the core idea of link-based ranking remains a foundation of web search and SEO.

6. Binary Search & Hashing (Fundamental Searching) – Binary search (first proposed around 1946) is the classic method to find an item in a sorted array in O(log n) time by repeatedly halving the search interval​. This simple yet powerful algorithm is fundamental to countless applications, from looking up words in a dictionary to database indexing, and it illustrated the immense efficiency gain from algorithmic thinking (searching 1 million elements in ~20 steps instead of linear scanning). Hashing (Hash Tables), introduced by H. P. Luhn in 1953​, takes searching a step further by achieving average-case O(1) lookups. By mapping keys to array indices via a hash function, hash tables enable constant-time insertion and retrieval in practice​. Hash-based structures (like dictionaries or caches) are ubiquitous in software and systems. Together, binary search and hashing represent foundational techniques that drastically improved data retrieval efficiency; they are building blocks in everything from low-level library routines to high-level application code.

7. Shor’s Algorithm (Quantum Factoring) – Shor’s algorithm (Peter Shor, 1994) demonstrated the disruptive potential of quantum computing by providing a polynomial-time method for factoring large integers​. Before Shor, factoring (and the related discrete log problem) was believed to require super-polynomial time, forming the security basis of RSA and other cryptosystems. Shor’s quantum algorithm, however, can factor an n-bit number in roughly O(n² log n) time (using quantum Fourier transforms), exploiting quantum parallelism to achieve a superpolynomial speedup over known classical algorithms​. In principle, this means a quantum computer could break RSA encryption by factoring its large key moduli​. While large-scale quantum machines do not yet exist, Shor’s paper galvanized research in quantum computing and post-quantum cryptography. It remains one of the most influential algorithms in theory – showing that public-key cryptography could be rendered obsolete and thus driving the development of quantum-resistant encryption.

8. Advanced Encryption Standard (AES) – AES is the predominant symmetric encryption algorithm in use today, approved as a U.S. federal standard in 2001. It is a block cipher that encrypts data in 128-bit blocks using a key of 128, 192, or 256 bits​. AES was chosen for its combination of security and performance: it’s efficient on a wide range of hardware (from smartcards to CPUs) and has stood up to extensive cryptanalysis – no practical attacks are known against its full rounds. AES superseded the older DES algorithm in 2001 and was the first publicly accessible cipher endorsed by the NSA for top-secret information​. Today, AES is everywhere: it secures Wi-Fi and disk encryption, protects financial transactions, and ensures data privacy in applications we use daily. Its design (the Rijndael algorithm by Daemen and Rijmen) introduced modern substitutions-permutation network techniques now fundamental in cryptography​. AES’s ubiquity and longevity as a standard highlight its immense influence on ensuring confidential communication in the modern world.

9. Gradient Descent (Optimization) – Gradient descent is a general-purpose optimization algorithm dating back to Cauchy in 1847, but it has become especially influential as the engine of modern machine learning. The idea is simple: iteratively adjust parameters in the opposite direction of the gradient of the objective function to minimize error. Each update is O(n) for n parameters, but gradient descent scales to very high-dimensional problems and can handle streaming data (as in stochastic gradient descent). It enabled the training of complex models by breaking the process into many small, incremental improvements. Stochastic Gradient Descent (SGD) and variants like Adam are the workhorses for training deep neural networks – virtually every neural model (CNNs, RNNs, transformers) is trained via gradient descent or a close cousin​. Beyond machine learning, gradient methods dominate in fields like convex optimization and control. The algorithm’s impact lies in its generality and efficiency: from linear regression to billion-parameter deep nets, gradient descent provides a tractable way to solve huge optimization problems that were once thought impractical.

10. Transformer (Self-Attention Model) – The Transformer is a deep learning model introduced by Vaswani et al. in 2017 that has redefined the state of the art in natural language processing​. Unlike previous sequence models (RNNs or CNNs), the transformer relies entirely on a mechanism called self-attention to capture relationships in data, dispensing with recurrence and convolution​. This design allows for much greater parallelization during training and better long-range dependency modeling. In the original paper “Attention Is All You Need,” the transformer achieved superior accuracy in machine translation with significantly less training time compared to older architectures​. Its encoder-decoder architecture with multi-head attention and positional encodings has since become the foundation for NLP: models like BERT and GPT are built on the transformer framework. Beyond NLP, transformers are being applied to images, audio, and even protein sequences. The transformer’s rise has been extremely rapid – in just a few years, it has revolutionized NLP and enabled breakthroughs like accurate language understanding and generative AI (e.g. GPT-3 and beyond) that were previously unattainable.

11. Grover’s Algorithm (Quantum Search) – Grover’s algorithm (Lov Grover, 1996) is a quantum algorithm that yields a quadratic speedup for unstructured search problems. It finds a target entry in an unsorted list of N items in O(√N) steps​, whereas a classical search would take O(N) time on average to check each item​. Grover’s method uses quantum superposition and amplitude amplification to boost the probability of the correct answer and is proven optimal — no quantum algorithm can search unsorted data faster than the order of √N queries​. While a quadratic speedup is more modest than the exponential speedups of some other quantum algorithms, Grover’s algorithm has broad applicability. In cryptography, for example, it implies that brute-force attacks on symmetric ciphers or hash functions are about √N times faster with a quantum computer (meaning a 128-bit key has an effective quantum security of 64 bits). Grover’s algorithm is a cornerstone of quantum computing theory, showcasing a clear advantage over classical computing for a wide class of search problems and influencing quantum algorithm design in various domains.

12. A Search (Heuristic Pathfinding)* – A** (pronounced “A-star”) is a pathfinding and graph traversal algorithm formulated in 1968 (Hart, Nilsson, Raphael) that efficiently finds the least-cost path from a start to a goal node. It extends Dijkstra’s algorithm by incorporating a heuristic estimate of the distance to the goal, which speeds up the search by prioritizing promising paths​. If the heuristic is admissible (never overestimates the true remaining cost), A* is guaranteed to find an optimal path, and it will do so faster than an uninformed search by avoiding exploring unnecessary branches​. In practice, A* is widely used in AI and operations research: it plans robot motion and vehicle routes, computes optimal paths in video game maps, and solves puzzle searches. Its versatility and efficiency have made it the default choice for pathfinding in many domains​. A*’s key contribution was combining the strengths of Dijkstra’s algorithm (optimality) and heuristic search (direction toward goal) – an approach that has influenced almost all subsequent heuristic graph search algorithms.

13. SHA-256 (Cryptographic Hash) – SHA-256 is a cryptographic hash function released by NIST in 2001 as part of the SHA-2 family​. It takes an arbitrary input and produces a 256-bit (32-byte) fixed-size output. SHA-256 is designed to be one-way (irreversible) and collision-resistant: finding two different inputs with the same output or recovering the input from the output is computationally infeasible. It has proven to be one of the most widely used hash algorithms in practice​, employed in virtually all modern security protocols and applications. For example, SHA-256 secures password storage and digital signatures by ensuring data integrity​– any change to the data produces a completely different hash. It’s also integral to blockchain technologies like Bitcoin, where it serves both to link blocks together and as the proof-of-work puzzle (miners must find a hash below a target value)​. The algorithm’s balance of speed and security has kept it unbroken and at the core of Internet security for over two decades. As a testament to its influence, SHA-256 (and its SHA-2 variants) is mandated in government and industry standards, making it a foundation of modern cybersecurity.

14. Reinforcement Learning (Q-Learning) – Reinforcement learning (RL) algorithms enable an agent to learn optimal behavior through feedback from interactions with an environment. Among these, Q-learning (Watkins, 1989) is a seminal model-free RL algorithm that learns an action-value function Q(s, a), which estimates the long-term reward of taking action a in state s. By iteratively updating Q-values using the Bellman equation, Q-learning provably converges to the optimal policy for a given Markov Decision Process​, without requiring a model of the environment. The influence of RL exploded when such algorithms began to achieve superhuman results in challenging domains – notably, Google DeepMind’s AlphaGo used deep reinforcement learning to master the game of Go, a milestone in AI achieved in 2016​. Today, RL techniques are used in robotics (for learning locomotion and control policies), in recommendation systems and advertising, in resource management (e.g. job scheduling), and in games beyond Go (e.g. AlphaStar for StarCraft). By learning from rewards and penalties, reinforcement learning algorithms introduced a powerful paradigm for autonomous decision-making, complementing supervised and unsupervised learning in AI.

15. Genetic Algorithms (Evolutionary Optimization) – Genetic Algorithms (GAs), formalized by John Holland in 1975, pioneered the field of evolutionary computation​. GAs solve optimization problems by mimicking natural selection: they maintain a population of candidate solutions and evolve it over many generations. Each generation is produced by selecting the fittest individuals and applying crossover (recombining parts of two solutions) and mutation (randomly altering a solution) to create new candidates​. Over time, the population “evolves” better and better solutions. The genetic algorithm’s stochastic yet directed search is especially useful for complex or poorly understood search spaces where traditional algorithms falter – for example, GAs have been used to design innovative antennas (as NASA did with an evolved spacecraft antenna)​, optimize scheduling and routing, and even evolve neural network architectures. While not guaranteed to find the perfect solution, GAs often find good solutions within feasible time for NP-hard problems. Their introduction was hugely influential academically: they opened up bio-inspired computing and led to numerous variants (genetic programming, evolutionary strategies, etc.). In practice, genetic algorithms continue to be a go-to heuristic for engineers and researchers tackling optimization problems where an “outside-the-box” search approach is needed.