☕ Buy me a coffee — $3

Introduction to Algorithms

What Are Algorithms?

An algorithm is a finite sequence of well-defined instructions, typically used to solve a class of specific problems or to perform a computation. At its core, an algorithm is a step-by-step procedure for solving a problem. Think of it as a recipe: just as a recipe provides instructions for cooking a dish, an algorithm provides instructions for solving a computational problem.

Algorithms are fundamental to computer science and programming. While there can be an infinite number of algorithms, in practice, only a few hundred are repeatedly used across different domains. Understanding these core algorithms and when to apply them is essential for becoming an effective programmer and problem solver.

Algorithms exist everywhere in our daily lives, from the route your GPS calculates to the way search engines rank results, from social media feeds to recommendation systems. In computer science, algorithms are the building blocks that enable software to process data, make decisions, and solve complex problems efficiently.

Where the Word "Algorithm" Comes From

The word "algorithm" is a corruption of the name of the 9th-century Persian mathematician Abū ʿAbd Allāh Muḥammad ibn Mūsā al-Khwārizmī, who lived in Baghdad around 780–850 CE. Al-Khwārizmī wrote several foundational mathematical texts, including one on Hindu-Arabic numerals that was later translated into Latin as Algoritmi de numero Indorum. Medieval European mathematicians used the Latin "algorismus" to mean the specific procedure for arithmetic using the Hindu-Arabic decimal system, and the word gradually generalised to mean any step-by-step procedure. The modern spelling "algorithm" was influenced by a false etymology connecting it to the Greek word arithmos (number).

Al-Khwārizmī's other famous book, al-Kitāb al-Muḫtaṣar fī Ḥisāb al-Jabr wa-l-Muqābala, gave the word "algebra" to the world by the same process: the Latin translation of its title. So two of the most fundamental words in mathematics and computer science both trace to the same 9th-century Baghdad scholar, whose name has become synonymous with the very idea of systematic calculation.

The concept of an algorithm long predates the word for it. Euclid's algorithm for computing the greatest common divisor, published in Elements around 300 BCE, is still taught today and remains the most efficient known method. Eratosthenes' Sieve for finding prime numbers dates to roughly the same period. The abstract idea of a mechanical, step-by-step procedure for solving problems is one of the oldest in intellectual history, older than calculus, older than algebra, older than any named branch of mathematics.

The Modern Theoretical Foundations

Modern algorithm theory rests on a small number of insights developed in the 1930s and 1940s that transformed the informal notion of "calculation" into a precise mathematical concept.

Alan Turing's 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem" introduced the abstract machine now called the Turing machine and used it to define what it means for a problem to be "computable" at all. Turing's insight was that any effective procedure, any algorithm in the intuitive sense, can be carried out by a very simple abstract machine that reads and writes symbols on an infinite tape according to a finite table of rules. This gave the first precise definition of what an algorithm is, and it revealed that some problems are algorithmically unsolvable in principle, no algorithm can exist for them, no matter how clever.

Alonzo Church independently formalised the same concept using a different formalism, the lambda calculus, at essentially the same time. The equivalence of these formalisms (any function computable by a Turing machine is definable in lambda calculus, and vice versa) is the origin of the Church-Turing thesis: the informal notion of "algorithm" is captured precisely by either of these models, and by extension by any modern programming language. The Church-Turing thesis is not a theorem, it cannot be, since it relates an informal notion to a formal one, but it is one of the deepest empirical observations in the sciences: every attempt to define "computability" rigorously has arrived at the same class of functions.

Donald Knuth, starting in the 1960s and continuing to the present, established the modern discipline of algorithm analysis, the study of how algorithms behave, not just whether they work. Knuth's multi-volume The Art of Computer Programming, unfinished since 1968, is the reference that defined how algorithms should be described, analysed, and compared. Every algorithm chapter on this site is, in some sense, a footnote to Knuth.

Key Properties of Algorithms

For a procedure to be considered a valid algorithm, it must possess certain key properties:

  • Finiteness: An algorithm must terminate after a finite number of steps. It cannot run indefinitely.
  • Definiteness: Each step must be precisely defined. There should be no ambiguity about what each instruction means.
  • Input: An algorithm has zero or more inputs, which are values supplied to the algorithm before it begins.
  • Output: An algorithm produces one or more outputs, which are the results of the computation.
  • Effectiveness: Each operation must be basic enough that it can be performed exactly and in a finite amount of time.

These five properties, first articulated in this form by Knuth in the 1960s, distinguish an algorithm from other kinds of procedure. A recipe that includes "season to taste" fails definiteness. A physics formula involving real-number computations that cannot terminate exactly fails effectiveness. An infinite loop fails finiteness. Every actual algorithm implementable on a computer satisfies all five.

An interesting boundary case: what about a program that performs some correct computation but has a bug that makes it fail on certain inputs? Is it an algorithm? In the technical sense, yes, it satisfies the five properties for the inputs on which it terminates and produces correct output. In the practical sense, of course not, a "buggy algorithm" is only an algorithm within the domain of inputs it handles. This gap between the theoretical and practical notions of "algorithm" is why software engineering has a whole discipline of testing, verification, and formal methods around it.

The Limits: Problems No Algorithm Can Solve

A striking consequence of Turing's 1936 paper is that some problems are algorithmically unsolvable in principle. This is not a statement about current technology being inadequate or programmers being insufficiently clever, it is a mathematical proof that no algorithm can exist for these problems, ever, on any machine.

The canonical example is the Halting Problem: given an arbitrary program and an arbitrary input, decide whether the program will eventually halt or will run forever. Turing proved that no algorithm can solve this problem for all programs. The proof is a lovely piece of self-referential reasoning: suppose an algorithm HALT(P, x) exists that correctly answers "yes" or "no" for any program P and input x. Construct a new program D(P) that runs HALT(P, P) and does the opposite, if HALT says P halts, D loops forever; if HALT says P loops forever, D halts. Now what does HALT(D, D) return? Whatever it returns, D does the opposite, which contradicts HALT's correctness. So HALT cannot exist.

The Halting Problem is not just an abstract curiosity. It implies that many practical questions in programming are unsolvable in general: given a program, does it produce a specific output? Does it contain a bug that will trigger under some input? Is it equivalent to another program? All of these are unsolvable in the fully general case, which is why perfect static analysis, perfect optimising compilers, and perfect bug detectors do not exist. Real tools work by approximating, solving the problem for common patterns and giving up gracefully on the edge cases where a perfect answer would require solving the Halting Problem.

A second landmark result: many problems are algorithmically solvable but require exponential time in the worst case, and it is widely believed that no polynomial-time algorithm can exist. These are the NP-hard problems, travelling salesman, boolean satisfiability, graph colouring, integer programming. Whether P = NP (whether every problem whose solution can be quickly verified can also be quickly solved) is the most famous open problem in computer science and the Clay Mathematics Institute's Millennium Prize offers a million dollars for a proof either way. Most researchers believe P ≠ NP, which would mean these problems are inherently hard and we can only hope for good approximations.

Algorithm Design Principles

Effective algorithm design follows several key principles that help create efficient and correct solutions:

1. Problem Analysis

Before designing an algorithm, thoroughly understand the problem:

  • What are the inputs and expected outputs?
  • What are the constraints and edge cases?
  • What is the problem's complexity and scale?

2. Algorithmic Paradigms

Common approaches to algorithm design include:

  • Brute Force: Try all possible solutions (often inefficient but simple)
  • Greedy: Make locally optimal choices at each step
  • Divide and Conquer: Break problem into smaller subproblems
  • Dynamic Programming: Solve overlapping subproblems efficiently
  • Backtracking: Try solutions and undo if they don't work

3. Efficiency Considerations

When designing algorithms, consider:

  • Time Complexity: How long does the algorithm take to run?
  • Space Complexity: How much memory does the algorithm require?
  • Scalability: How does performance change with input size?

We'll dive deeper into complexity analysis in Complexity Analysis.

Real-World Applications of Algorithms

Algorithms power many technologies we use daily:

Search and Recommendation

  • Search Engines: Use ranking algorithms to find and prioritize relevant results
  • Recommendation Systems: Netflix, Amazon, and Spotify use collaborative filtering algorithms
  • Social Media Feeds: Algorithms determine what content you see and in what order

Navigation and Routing

  • GPS Navigation: Uses shortest path algorithms (like Dijkstra's) to find optimal routes
  • Ride-Sharing: Algorithms match drivers with passengers and optimize routes
  • Logistics: Delivery companies use algorithms to optimize package routing

Data Processing

  • Database Systems: Use sorting and searching algorithms for efficient data retrieval
  • Image Processing: Algorithms for compression, filtering, and recognition
  • Cryptography: Encryption algorithms secure our digital communications

Machine Learning and AI

  • Neural Networks: Training algorithms optimize model parameters
  • Natural Language Processing: Algorithms process and understand human language
  • Computer Vision: Algorithms identify and classify objects in images

Simple Algorithm Example

Let's look at a simple algorithm: finding the maximum value in an array. 


Algorithm: Find Maximum
Input: Array A of n numbers
Output: Maximum value in A

1. Set max = A[0]
2. For i = 1 to n-1:
   a. If A[i] > max:
      Set max = A[i]
3. Return max

This algorithm demonstrates the key properties:

  • Finiteness: It loops exactly n-1 times
  • Definiteness: Each step is clear and unambiguous
  • Input: Takes an array A
  • Output: Returns the maximum value
  • Effectiveness: Each operation (comparison, assignment) is basic

What's Next?

Now that you understand what algorithms are, the next step is learning how to analyze their efficiency. In Complexity Analysis, you'll learn about Big O notation, time complexity, space complexity, and how to compare different algorithms.

You can also explore specific algorithm categories: