---
title: 'What Is an Algorithm'
source: 'https://academia.sh/en/courses/algorithms/what-is-an-algorithm'
course: Algorithms
language: en
updated: '2026-08-17T18:07:35+00:00'
license: 'CC BY-SA 4.0'
---

# What Is an Algorithm

The criteria for an algorithm, the distinction between correctness and termination, the model of computation, and why measuring running time is not enough.

The Data Structures course established how data is organized and how that
organization determines cost. Cost expressions — $O(1)$, $O(\log n)$, $O(n)$ — were
used but not defined; they were explained only intuitively, as "the rate at which
cost grows as data grows."

This course closes that gap and turns the question around: what is examined is not
the data but the **solution**. How are different solutions to the same problem
compared, and what is the comparison based on?

## The Criteria for an Algorithm

An **algorithm** is a finite sequence of steps that solves a problem. Short as this
definition is, five criteria are required for a method to count as an algorithm:

**Input.** It takes zero or more well-defined inputs.

**Output.** It produces at least one output, and that output is related to the input.

**Determinism.** Every step has a single meaning; the same input executes the same
steps in the same order. The determinism discussion from the Programming
Fundamentals course connects here.

**Finiteness.** It halts in a finite number of steps for every valid input. A method
that enters an infinite loop is not an algorithm.

**Effectiveness.** Every step must be executable in finite time with well-defined
means. "Find the right answer" is not a step; "scan the array from start to end" is a
step.

The five criteria do not cover everything called an "algorithm" in everyday language.
Randomized methods relax the determinism criterion; approximate methods relax the
exactness of the output. These relaxations are stated explicitly wherever they apply.

## Problem, Instance, and Program

These three concepts are often confused, and their distinction is assumed throughout
the rest of this course.

A **problem** is the specification of the relationship between inputs and acceptable
outputs: "the input is an array of integers; the output is the same elements arranged
in nondecreasing order." A specification does not state a method; it only states what
counts as correct.

An **instance** is a single input to the problem: the array `[5, 2, 9]` is an
instance. An algorithm must solve **every** instance, not a single one; giving the
right answer on one particular input is not enough.

A **program** is an implementation of an algorithm, written in a particular language
for a particular machine. The same algorithm can have countless programs; they are
all the same algorithm as long as they follow the same steps.

This distinction determines what correctness is measured against: an algorithm is
correct not relative to a program but relative to the **problem specification**. This
is why algorithms are usually written in pseudocode — language details are
irrelevant to the specification.

## Correctness Has Two Parts

Saying an algorithm is correct makes two separate claims:

**Partial correctness:** If the algorithm **halts**, the result is correct.

**Termination:** The algorithm halts for every valid input.

Together the two give **total correctness**. The distinction lets proofs be split
into two separate parts as well, and this split is useful in practice — there are
methods that satisfy one but not the other.

The standard tool for partial correctness is the **loop invariant**, introduced in
the Programming Fundamentals course: if a condition is true before the loop is
entered, preserved on every iteration, and yields the desired result when the loop
ends, partial correctness has been proved.

The standard tool for termination is a **decreasing measure**: if a value can be
found that strictly decreases on every iteration and is bounded from below, the loop
cannot continue forever.

```python
def find_largest(measurements: list[int]) -> int:
    """Returns the largest measurement. The list must not be empty.

    Invariant: at the start of every iteration, `largest` is the
    largest of the elements visited so far.
    Termination: the number of remaining elements decreases by one every iteration.
    """
    largest = measurements[0]
    for measurement in measurements:
        if measurement > largest:
            largest = measurement
    return largest


print(find_largest([12, 18, 7, 25, 14]))     # 25
```

The two lines in the docstring are not decoration: one is the justification for
partial correctness, the other for termination. Showing that an algorithm is correct
means being able to write these two sentences.

## Same Problem, Different Algorithms

A problem can have more than one solution, and solutions differ not only in speed but
in **structure**.

```python
def sum_loop(n: int) -> int:
    """The sum of the numbers from 1 to n; each number added one at a time."""
    total = 0
    for i in range(1, n + 1):
        total += i
    return total


def sum_formula(n: int) -> int:
    """The same sum; in a single step with a closed-form formula."""
    return n * (n + 1) // 2


print(sum_loop(100), sum_formula(100))                # 5050 5050
print(sum_loop(1_000_000) == sum_formula(1_000_000))  # True
```

The two functions give the same result. The first does $n$ additions; the second does
one multiplication, one addition, and one division — regardless of the input.

The difference is not an optimization detail: the first solution's cost grows with
the input, the second's does not. For a million, the first does a million
operations, the second does three.

This makes the course's central question concrete: **how do we measure** the
difference between two solutions?

## Why Measuring Time Is Not Enough

The first metric that comes to mind is running time. But time depends on three
factors at once, and none of them belongs to the algorithm itself.

**Hardware.** The same program takes different amounts of time on different
processors; the memory hierarchy from the How Computers Work course was one source
of this difference.

**Implementation.** Choices of language, compiler, and runtime change duration by
multiples. In the cache measurement from the Data Structures course, this effect was
large enough to hide what was meant to be measured.

**Input.** The same algorithm takes different amounts of time on different inputs; a
sorted array and a scrambled array behave very differently under the same sorting
algorithm.

A measurement is therefore not a **property** of an algorithm but an observation of a
particular run. For a comparison to be portable, a metric independent of hardware and
language is needed.

## Model of Computation and Operation Counting

The solution is to adopt an abstract **model of computation**. The model used in this
course rests on these assumptions:

- Basic operations — addition, comparison, assignment, index access — take constant
  time.
- Memory access has the same cost regardless of location.
- Operations execute one after another.

The model is a simplified version of reality: cache layers and the instruction
pipeline are ignored. In return, algorithms become comparable independently of
hardware.

The metric follows from this: **the number of basic operations performed as a
function of input size.**

```python
def linear_search(array: list[int], target: int) -> tuple[int, int]:
    """Returns (index found or -1, comparison count)."""
    comparisons = 0
    for i, value in enumerate(array):
        comparisons += 1
        if value == target:
            return i, comparisons
    return -1, comparisons


array = list(range(1000))
print(linear_search(array, 0))       # (0, 1)      — best case
print(linear_search(array, 999))     # (999, 1000) — worst case
print(linear_search(array, -1))      # (-1, 1000)  — not found
```

The same algorithm, at the same input size, does anywhere from 1 to 1000 operations.
For this reason, three separate metrics are defined instead of a single number:

- **Best case:** The input that requires the fewest operations.
- **Worst case:** The input that requires the most operations.
- **Average case:** The expected number of operations over a probability
  distribution of inputs.

The default metric is the **worst case**; it gives a guarantee and requires no
assumption about distribution. Average case is meaningful when the distribution is
actually known — the hash table's "average constant" promise was exactly this kind of
claim.

## Summary

- An algorithm is a finite sequence of steps that meets the criteria of input,
  output, determinism, finiteness, and effectiveness.
- A problem is a specification, an instance is a single input, a program is an
  implementation; correctness is measured against the specification.
- Correctness has two parts: partial correctness (the result is correct if it
  halts) is justified with a loop invariant, and termination (it halts for every
  input) with a decreasing measure.
- Solutions to the same problem differ in structure; the difference shows up in
  whether cost grows with the input or not.
- Running time depends on hardware, implementation, and input; it is not a property
  of the algorithm.
- The metric is the number of basic operations performed as a function of input
  size in an abstract model, and best, worst, and average case are treated
  separately.

## Next Step

Operation counting is a step in the right direction, but it still drowns in detail:
in a thousand-element array, whether 1000 or 1002 comparisons were made does not
matter. The next lesson eliminates this detail and formally defines the notation that
keeps only the growth rate — asymptotic notation.