Notable Algorithms

Introduction

An algorithm is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of problems or to perform a computation. Algorithms are central to modern computing, serving as the mathematical backbone of everything from simple sorting routines to large-scale machine learning models.

This entry surveys some of the most historically significant and practically impactful algorithms across computer science, mathematics, and artificial intelligence. Each entry includes its origin, time/space complexity, and primary applications.

Classical Foundations

These algorithms established the theoretical groundwork for modern computational theory and remain staples in computer science curricula worldwide.

Euclidean Algorithm

Number TheoryAncient

📆 ~300 BCE👤 Euclid of Alexandria

The oldest known algorithm, used to compute the greatest common divisor (GCD) of two integers. It operates on the principle that the GCD of two numbers also divides their difference.

TimeO(log(min(a,b)))

SpaceO(1)

QuickSort

SortingDivide & Conquer

📆 1959👤 Tony Hoare

A highly efficient comparison-based sorting algorithm that works by selecting a 'pivot' element and partitioning the array around it. Despite a worst-case O(n²), its average-case performance and in-place nature make it the default sort in many standard libraries.

Avg TimeO(n log n)

Worst TimeO(n²)

SpaceO(log n)

Fast Fourier Transform (FFT)

Signal ProcessingMath

📆 1965👤 Cooley & Tukey

An algorithm that computes the Discrete Fourier Transform (DFT) efficiently. It reduces the complexity from O(n²) to O(n log n), revolutionizing digital signal processing, image compression, and numerical analysis.

TimeO(n log n)

SpaceO(n)

Graph & Search Algorithms

Essential for networking, route optimization, game AI, and data structure traversal.

Dijkstra's Algorithm

GraphShortest Path

📆 1956👤 Edsger W. Dijkstra

Finds the shortest path between a source node and all other nodes in a weighted graph with non-negative edges. Widely used in GPS navigation, network routing protocols (OSPF, IS-IS), and logistics optimization.

Time (Fib Heap)O(E + V log V)

SpaceO(V)

A* Search

HeuristicPathfinding

📆 1968👤 Hart, Nilsson, Raphael

An informed search algorithm that uses a heuristic function to estimate the cost to reach the goal, making it significantly faster than Dijkstra's for many practical pathfinding problems, especially in games and robotics.

TimeO(E)

SpaceO(V)

Cryptography & Security

Algorithms that form the bedrock of digital trust, secure communications, and blockchain technology.

RSA (Rivest–Shamir–Adleman)

Public-KeyAsymmetric

📆 1977👤 R, S, & A

One of the first public-key cryptosystems and widely used for secure data transmission. Its security relies on the practical difficulty of factoring the product of two large prime numbers.

Key GenO(k³)

EncryptionO(k³)

DecryptionO(k³)

Modern & AI Algorithms

Recent breakthroughs driving the current wave of artificial intelligence and machine learning.

Transformer Attention (Scaled Dot-Product)

Deep LearningNLP

📆 2017👤 Vaswani et al. (Google)

The core mechanism behind the Transformer architecture. It computes attention weights by calculating the dot product of query and key vectors, scaled by the square root of the key dimension, then applies softmax and multiplies by value vectors. Enabled BERT, GPT, and modern LLMs.

# Simplified Attention Mechanism
def scaled_dot_product_attention(Q, K, V, mask=None):
    d_k = K.shape[-1]
    scores = torch.matmul(Q, K.transpose(-2, -1)) / math.sqrt(d_k)
    if mask is not None:
        scores = scores.masked_fill(mask == 0, -1e9)
    attn = torch.softmax(scores, dim=-1)
    return torch.matmul(attn, V)

TimeO(seq² × d)

SpaceO(seq²)

Complexity & Analysis

Algorithm efficiency is typically measured using Big O notation, which describes the upper bound of time or space requirements as input size grows. Understanding complexity classes helps practitioners choose the right algorithm for scale-constrained environments.

Common Complexity Classes

O(1)Constant

O(log n)Logarithmic

O(n)Linear

O(n log n)Linearithmic

O(n²)Quadratic

O(2ⁿ)Exponential

References & Further Reading

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
Vaswani, A., et al. (2017). "Attention Is All You Need". NeurIPS.
Rivest, R. L., Shamir, A., & Adleman, L. (1978). "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems". Communications of the ACM.
Knuth, D. E. (1997). The Art of Computer Programming. Addison-Wesley.