What is an Algorithm?

Overview

An algorithm is an abstract mathematical object — a finite, deterministic sequence of unambiguous steps that accepts zero or more inputs and produces at least one output whose relationship to the input is mathematically defined. Unlike a program, it is independent of any specific language or hardware.

Without formal algorithms, software degrades unpredictably at scale. Formalizing a solution guarantees correctness across all valid inputs, converts intuitive guessing into a mathematically verifiable procedure, and enables rigorous analysis of time and space efficiency using asymptotic notation.

Where used: Network routing: algorithms like Dijkstra's compute optimal paths across dynamic router topologies, Database engines: B-tree algorithms resolve queries in O(log n) instead of O(n) sequential scans

Why learn this

• It is the foundational mental model that separates ad-hoc coders from rigorous software engineers.
• Every technical interview at top-tier firms evaluates finiteness, definiteness, and efficiency before a line of code is written.
• Understanding what makes a procedure an algorithm — versus a heuristic or a reactive process — prevents an entire class of design errors.

Aha moment

# Both terminate and produce correct output. Which is an 'algorithm'?
def gcd_brute(a, b):
    for i in range(min(a, b), 0, -1):
        if a % i == 0 and b % i == 0:
            return i

def gcd_euclid(a, b):
    while b:
        a, b = b, a % b
    return a

Prediction: Both functions return the same correct GCD. Both are algorithms.

Common guess: Only gcd_euclid is a real algorithm because it's faster.

Both are valid algorithms — they are both finite, definite, accept input, produce output, and are effective. 'Algorithm' is a correctness property, not an efficiency property. The difference between them is in their asymptotic complexity (O(n) vs O(log n)), not their algorithmic status.

Common mistakes

• Conflating an algorithm with a program: A program is a concrete implementation bound by a specific language's syntax and a machine's physical limitations. An algorithm is an abstract mathematical entity whose correctness and efficiency can be reasoned about independently of any compiler or hardware.
• Treating server listener loops as algorithms: A procedure that runs indefinitely — such as an event listener or OS process — violates the finiteness property. Such constructs are reactive operating systems, not algorithms in the strict mathematical sense.
• Jumping to code before defining inputs, outputs, and constraints: Top-tier interviewers expect candidates to explicitly state input size and constraints, define the expected output relationship, and analyze Big-O complexity before writing a single line. Skipping this signals an inability to design generalizable solutions.

Glossary

deterministic sequence

A series of steps that will always produce the exact same result given the exact same starting point.

heuristic

A rule-of-thumb approach that tries to find a good enough answer quickly, but isn't guaranteed to find the perfect one.

asymptotic notation

A mathematical way to describe how an algorithm's performance changes as input size grows.

Recall questions

• Name Knuth's five properties that every true algorithm must exhibit.
• What is the key distinction between an algorithm and a computer program?
• Why are heuristics used instead of algorithms for tasks like generating natural-sounding poetry?

Understanding checks

A candidate says: 'My server's request-handling loop is an algorithm because it follows a finite set of rules per request.' What property of a true algorithm does this violate, and why?

It violates finiteness. The loop as a whole runs indefinitely — it never terminates after a finite total number of steps. Each individual request handler may be finite, but the enclosing server process is a reactive operating procedure, not an algorithm.

Finiteness requires the entire procedure to halt after a bounded number of steps regardless of input. An infinite listener loop structurally cannot satisfy this property.

You need to find the GCD of two integers. Should you use Euclid's algorithm or a brute-force scan from 1 to min(a, b)? Justify using at least two of Knuth's five properties.

Euclid's algorithm. Both satisfy finiteness and effectiveness, but Euclid's is vastly superior in efficiency — O(log min(a, b)) versus O(min(a, b)) — while remaining equally definite and effective. The brute-force scan violates no formal property but is impractical at scale.

Choosing between correct algorithms requires comparing their efficiency profiles. Understanding all five properties enables a candidate to reason about why one formally correct design outperforms another.

Practice tasks

Classify and justify: algorithm or not?

Given the three code snippets below (an infinite event loop, a recursive Fibonacci with no base case, and a standard binary search), classify each as a true algorithm or not, citing the specific Knuth property each violates. Modify the non-algorithms to fix the violation.

Continue learning

Next: Tracing State & Loop Invariants

Next: Iteration & Traversal

Return to DSA Roadmap