What Is an Algorithm?

An algorithm is a finite sequence of well-defined steps that takes some input and produces the correct output for every valid input. A program is an algorithm written in a particular language for a particular machine; the algorithm itself is the idea.

#The five properties (Knuth)

"Keep stirring until it tastes good" fails definiteness. A loop that may never end fails finiteness.

#The design and analysis process

1. Understand the problem — inputs, outputs, constraints, edge cases.
2. Choose a design technique — brute force, divide and conquer, greedy, dynamic programming, backtracking …
3. Write the algorithm — usually in pseudocode.
4. Prove it correct for all inputs.
5. Analyse its time and space as a function of the input size n.
6. Implement and test.

#Pseudocode

Pseudocode describes an algorithm without the noise of a real language:

INSERTION-SORT(A, n)
    for j = 2 to n
        key = A[j]
        i = j - 1
        while i > 0 and A[i] > key
            A[i + 1] = A[i]
            i = i - 1
        A[i + 1] = key

(Textbooks like CLRS index arrays from 1. Translate carefully to 0-based code.)

#Proving correctness: loop invariants

A loop invariant is a statement that is true before every iteration of a loop. To prove an algorithm correct with one, show three things:

1. Initialisation — it is true before the first iteration.
2. Maintenance — if it is true before an iteration, it remains true before the next.
3. Termination — when the loop ends, the invariant gives a useful property that shows the algorithm is correct.

For insertion sort, the invariant is: at the start of each iteration, the subarray A[1..j−1] holds the original first j−1 elements in sorted order. When the loop ends with j = n + 1, the whole array is sorted.

#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
using namespace std;

void insertionSort(vector<int> &a) {
    for (size_t j = 1; j < a.size(); j++) {
        assert(is_sorted(a.begin(), a.begin() + j));     // the loop invariant, checked at run time
        int key = a[j];
        int i = (int)j - 1;
        while (i >= 0 && a[i] > key) { a[i + 1] = a[i]; i--; }
        a[i + 1] = key;
    }
}

int main() {
    vector<int> a = {31, 41, 59, 26, 41, 58};
    insertionSort(a);
    for (int x : a) cout << x << " ";
    cout << "\nsorted: " << boolalpha << is_sorted(a.begin(), a.end()) << endl;
    return 0;
}

26 31 41 41 58 59 
sorted: true

#The RAM model

To analyse algorithms independently of hardware, we use the Random Access Machine model:

• Each simple operation (arithmetic, comparison, assignment, array access, function call) takes one unit of time.
• Memory access is constant time.
• Instructions run one after another (no parallelism).

The running time T(n) is the number of unit steps for an input of size n. For example, insertion sort does about n²/4 comparisons on average, so T(n) grows like n².

#Why analyse at all?

Suppose computer A runs 10⁹ instructions/second and computer B only 10⁷ — 100 times slower. Sort 10 million numbers:

A better algorithm on a slow machine beats a worse algorithm on a fast machine by orders of magnitude. That is why this subject exists.