Chapter 1. Introduction to Algorithms
Foundations: what an algorithm is, how to measure its efficiency, and the data structures we will rely on.
What is in this chapter
Computers are fast, but algorithms are what make them useful. The same problem can admit algorithms whose running times differ by factors of millions on inputs that already fit comfortably in memory: sorting a billion records takes minutes with a good algorithm but centuries with a bad one. This chapter assembles the preliminaries that the rest of the book relies on:
- A working definition of an algorithm with Euclid's GCD as a running example.
- Asymptotic notation (Big-O, Big-Omega, Big-Theta) for describing growth rates.
- Worked complexity analyses of linear search, binary search, and the Tower of Hanoi.
- The basic data structures used throughout the book: linked lists, stacks, queues, binary search trees, and heaps.
Euclid's GCD
Euclid's GCD uses the mod operation to reduce the larger of two integers until the two are equal. This is the classical imperative form. In Chapter 2, the same idea is expressed as a search for the least vector in a lattice, yielding the LLP algorithm LLP-GCD.
Time complexity: $O(\log(\max(a, b)))$, where $a$ and $b$ are the two inputs.
int GCD(int a, int b) {
while (a != b) {
if (a > b) {
if (a % b == 0) { a = b; }
else { a = a % b; }
} else {
if (b % a == 0) { b = a; }
else { b = b % a; }
}
};
return a;
}
Factorial
Recursive factorial; the textbook example for the recursion form $T(n) = n \cdot T(n-1)$.
Time complexity: $O(n)$.
int Factorial(int n) {
if (n == 0) { return 1; };
return n * Factorial(n - 1);
}
LinearSearch
Linear scan for key in array $A$. Returns the first matching index, or $-1$. Worst case $O(n)$.
Time complexity: $O(n)$, where $n$ is the size of the array.
int LinearSearch(int[] A, int key) {
int i = 0;
while (i < A.length) {
if (A[i] == key) { return i; };
i = i + 1;
};
return -1;
}
MaxElement
One-pass scan for the maximum element.
Time complexity: $O(n)$, where $n$ is the size of the array.
int MaxElement(int[] A) {
int max = A[0];
int i = 1;
while (i < A.length) {
if (A[i] > max) { max = A[i]; };
i = i + 1;
};
return max;
}
BinarySearch
Recursive binary search on a sorted array, $O(\log n)$.
Time complexity: $O(\log n)$, where $n$ is the size of the array.
int BinarySearch(int[] A, int key, int low, int high) {
if (low > high) { return -1; };
int mid = (low + high) / 2;
if (A[mid] == key) { return mid; };
if (A[mid] > key) { return BinarySearch(A, key, low, mid - 1); };
return BinarySearch(A, key, mid + 1, high);
}
Towers of Hanoi
The canonical $T(n) = 2T(n-1) + 1$ recurrence; the body captures the recursive structure (the actual disk move appears as a comment in the base case).
Time complexity: $O(2^n)$ moves to relocate $n$ disks.
void Hanoi(int n, int source, int aux, int target) {
if (n == 1) {
// Move disk from `source` to `target`.
} else {
Hanoi(n - 1, source, target, aux);
// Move disk from `source` to `target`.
Hanoi(n - 1, aux, source, target);
}
}
NestedSum
A textbook $O(n^2)$ double loop, used to motivate Big-O analysis.
Time complexity: $O(n^2)$.
int NestedSum(int n) {
int total = 0;
int i = 0;
while (i < n) {
int j = 0;
while (j < n) {
total = total + i * j;
j = j + 1;
};
i = i + 1;
};
return total;
}
PairSum
Counts pairs $(i, j)$ with $i < j$ such that $A[i] + A[j] = $ target. Naive $O(n^2)$;
the classic two-pointer / hash-map improvement is left as an exercise in the book.
Time complexity: $O(n^2)$, where $n$ is the size of the array.
int PairSum(int[] A, int target) {
int count = 0;
int i = 0;
while (i < A.length) {
int j = i + 1;
while (j < A.length) {
if (A[i] + A[j] == target) { count = count + 1; };
j = j + 1;
};
i = i + 1;
};
return count;
}
MergeSort
Recursive divide-and-conquer sort, $O(n \log n)$. Uses an auxiliary Merge aux method
declared in the same class — an early example of LL's aux-method support.
Time complexity: $O(n \log n)$, where $n$ is the size of the array.
void MergeSort(int[] A, int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
MergeSort(A, low, mid);
MergeSort(A, mid + 1, high);
Merge(A, low, mid, high);
}
}
void Merge(int[] A, int low, int mid, int high) {
int[] B = new int[A.length];
forall k in [low..high] : B[k] = A[k];
int i = low;
int j = mid + 1;
int k = low;
while (i <= mid && j <= high) {
if (B[i] <= B[j]) {
A[k] = B[i];
i = i + 1;
} else {
A[k] = B[j];
j = j + 1;
};
k = k + 1;
};
while (i <= mid) {
A[k] = B[i];
i = i + 1;
k = k + 1;
};
while (j <= high) {
A[k] = B[j];
j = j + 1;
k = k + 1;
}
}
Heap
Min-heap operations on a flat array: heapify, build, insert,
extractMin. Heaps anchor Dijkstra and Prim later in the book.
Time complexity: build $O(n)$; heapify, insert, and extractMin are $O(\log n)$, where $n$ is the heap size.
class Heap {
void build(int[] A, int n) {
int i = n / 2 - 1;
while (i >= 0) {
heapify(A, i, n);
i = i - 1;
}
}
void heapify(int[] A, int i, int n) {
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && A[left] < A[smallest]) { smallest = left; };
if (right < n && A[right] < A[smallest]) { smallest = right; };
if (smallest != i) {
swap(A[i], A[smallest]);
heapify(A, smallest, n);
}
}
int insert(int[] A, int key, int n) {
n = n + 1;
int i = n - 1;
while (i > 0 && A[(i - 1) / 2] > key) {
A[i] = A[(i - 1) / 2];
i = (i - 1) / 2;
};
A[i] = key;
return n;
}
int extractMin(int[] A, int n) {
if (n < 1) { return -2147483648; };
int min = A[0];
A[0] = A[n - 1];
n = n - 1;
heapify(A, 0, n);
return min;
}
}
Looking ahead
The asymptotic vocabulary introduced in this chapter is used pervasively throughout the book. The data structures play their part as well: heaps anchor Dijkstra's algorithm in Chapter 7 (Shortest Paths), union-find drives Kruskal in Chapter 8 (MST), linked lists and arrays are the canonical input formats for the LLP algorithms of Chapter 2.