Computation Models and Asymptotic Analysis

What Is a Problem? What Is an Algorithm?

The word "algorithm" is used loosely everywhere. In this module, we use it precisely. Start with the distinction that matters most: a problem is not the same as an algorithm.

A problem is a binary relation — a specification mapping inputs to correct outputs. The problem does not say how to compute the answer, only what a correct answer looks like. Most interesting problems have infinitely many possible inputs, so we cannot just list every input-output pair. Instead, we give a verifiable predicate: a property that any correct output must satisfy.

An algorithm is a deterministic procedure: given an input, it produces exactly one output. An algorithm solves a problem if, for every possible input, it produces an output that satisfies the problem's correctness predicate.

The Birthday Matching Problem — A Running Example

Consider a concrete problem that will let us demonstrate correctness, efficiency, and data structure choice all at once.

Here is a straightforward algorithm: for each student, check all previously seen students for a birthday match. If a match is found, return the pair. If we finish without finding one, return None.

def birthday_match(students):
    """
    Find a pair of students sharing a birthday.
    Input:  tuple of (name, bday) tuples
    Output: tuple of two names, or None
    """
    n = len(students)                    # O(1)
    record = []                          # O(1)

    for k in range(n):                   # n iterations
        name1, bday1 = students[k]       # O(1)
        for i in range(k):               # k iterations
            name2, bday2 = record[i]     # O(1)
            if bday1 == bday2:           # O(1)
                return (name1, name2)    # O(1)
        record.append((name1, bday1))    # O(1) amortised

    return None                          # O(1)

#include <vector>
#include <string>
#include <optional>
using namespace std;

using Student = pair<string, string>;   // (name, birthday)
using Match   = pair<string, string>;

optional<Match> birthday_match(const vector<Student>& students) {
    int n = students.size();             // O(1)
    vector<Student> record;             // O(1)
    record.reserve(n);

    for (int k = 0; k < n; ++k) {      // n iterations
        const auto& [name1, bday1] = students[k];   // O(1)
        for (int i = 0; i < k; ++i) {               // k iterations
            const auto& [name2, bday2] = record[i]; // O(1)
            if (bday1 == bday2)                      // O(1)
                return Match{name1, name2};
        }
        record.push_back(students[k]);  // O(1) amortised
    }
    return nullopt;                     // O(1)
}

The outer loop runs $n$ times. For each iteration $k$, the inner loop runs $k$ times. Total operations:

Quadratic. For NSE's 10 crore events this is unusable — but let us prove it correct first, then improve it.

Proving Correctness — Induction Is the Only Tool

A program has fixed size but must work on arbitrarily large inputs. The only mathematical tool that connects a finite description to an infinite family of cases is induction. This is why recursion and loops are central to computer science — they are the syntactic form of induction.

For birthday_match, the invariant on the outer loop is: after $k$ iterations, record contains exactly the first $k$ students, and if any pair among them shares a birthday, we have already returned it.

Initialisation: Before any iteration ($k = 0$), record is empty — vacuously correct, no pairs to check.

Maintenance: At iteration $k$, the inner loop compares students[k] against every student in record (which holds students $0, \ldots, k{-}1$ by the inductive hypothesis). If a match exists involving student $k$, the inner loop finds it and returns. If not, we append student $k$ to record, preserving the invariant for $k+1$.

Termination: The loop ends at $k = n$. The invariant now says: record holds all $n$ students, and if any matching pair existed, it was already returned. So returning None is correct.

Efficiency — What Does "Fast" Mean?

We cannot measure time in seconds — that depends on hardware, compiler, system load. We want a machine-independent measure. The answer: count the number of fixed-time operations the algorithm performs, as a function of the input size $n$.

"Fixed-time" needs a precise model. We use the Word-RAM model.

Asymptotic Notation — Ignoring the Noise

We do not need the exact number of operations — we need the growth rate as $n$ gets large. Constant factors depend on the machine. Low-order terms become irrelevant for large $n$. Asymptotic notation captures exactly the part that matters.

The practical hierarchy, from fastest to slowest growth:

Improving Birthday Matching — Data Structures Change Everything

The naive algorithm is $\Theta(n^2)$ because checking "is bday1 in record?" takes $\Theta(k)$ time using a list. If we use a hash set — a data structure supporting $\Theta(1)$ expected lookup — the entire algorithm becomes $\Theta(n)$.

def birthday_match_fast(students):
    """
    Same problem, O(n) expected time using a hash map.
    """
    seen = {}                            # bday -> name, O(1) lookup

    for name, bday in students:         # n iterations
        if bday in seen:                 # O(1) expected
            return (seen[bday], name)    # match found
        seen[bday] = name               # O(1) expected

    return None

#include <unordered_map>
#include <vector>
#include <string>
#include <optional>
using namespace std;

using Student = pair<string, string>;
using Match   = pair<string, string>;

optional<Match> birthday_match_fast(const vector<Student>& students) {
    unordered_map<string, string> seen;  // bday -> name
    seen.reserve(students.size());        // avoid rehashing

    for (const auto& [name, bday] : students) {  // n iterations
        auto it = seen.find(bday);                // O(1) expected
        if (it != seen.end())
            return Match{it->second, name};
        seen[bday] = name;                        // O(1) expected
    }
    return nullopt;
}

Same problem. Same correctness proof structure. One data structure change: list → hash map. Runtime drops from $\Theta(n^2)$ to $\Theta(n)$ expected. We will prove why hash maps give $\Theta(1)$ expected lookup in Chapter 4. For now, accept it as the key lesson: the choice of data structure determines the complexity of your algorithm.

How to Solve an Algorithms Problem

Every algorithms problem you encounter — in this module, in interviews, in production — has the same two-step solution strategy.

Step 1: Reduce to a known problem. Can you map this problem onto something you already know how to solve efficiently? The whole point of building a library of data structures and algorithms is to have reductions available. "This is a shortest-path problem." "This is a priority queue problem." Recognising the structure is half the solution.

Step 2: Design your own recursive algorithm. If no known reduction applies, design from scratch. The standard techniques are: brute force (enumerate all possibilities), divide and conquer (split into subproblems, combine), dynamic programming (save subproblem solutions to avoid recomputation), and greedy (make locally optimal choices at each step). We will cover all of these in depth.