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(\min(a, b)))$, where $a$ and $b$ are the two inputs.

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.

MaxElement

One-pass scan for the maximum element.

Time complexity: $O(n)$, where $n$ is the size of the array.

BinarySearch

Recursive binary search on a sorted array, $O(\log n)$.

Time complexity: $O(\log n)$, where $n$ is the size of the array.

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.

NestedSum

A textbook $O(n^2)$ double loop, used to motivate Big-O analysis.

Time complexity: $O(n^2)$.

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.

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.

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.

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.