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 repeatedly subtracts the smaller of two integers from the larger 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 \min(a, b))$, where $a$ and $b$ are the two inputs.

int GCD(int a, int b) {
  while (a != b) {
    if (a > b) { a = a - b; };
    if (b > a) { 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 compute(int n) {
  if (n == 0) { return 1; };
  return n * compute(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 find(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 find(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 find(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 find(A, key, low, mid - 1); };
  return find(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 solve(int n, int source, int aux, int target) {
  if (n == 1) {
    // Move disk from `source` to `target`.
  } else {
    solve(n - 1, source, target, aux);
    // Move disk from `source` to `target`.
    solve(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 compute(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 count(int[] A, int target) {
  int c = 0;
  int i = 0;
  while (i < A.length) {
    int j = i + 1;
    while (j < A.length) {
      if (A[i] + A[j] == target) { c = c + 1; };
      j = j + 1;
    };
    i = i + 1;
  };
  return c;
}

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 sort(int[] A, int low, int high) {
  if (low < high) {
    int mid = (low + high) / 2;
    sort(A, low, mid);
    sort(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 9(Shortest Paths), union-find drives Kruskal in Chapter 10(MST), linked lists and arrays are the canonical input formats for the LLP algorithms of Chapter 2.