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.

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: two recursive calls on $n-1$ disks with a single move between them. Each call returns its own sequence of moves, so the result is the whole $2^n - 1$ move list.

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-Intro

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.