What Is an Algorithm

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.

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.

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.

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.