Preface

Algorithms with TypeScript is a free, comprehensive textbook covering algorithms and data structures from first principles to advanced topics. Spanning 22 chapters across six parts, it features idiomatic TypeScript 5 implementations, step-by-step complexity analysis, exercises, and a full test suite using Vitest — bridging the gap between academic Computer Science theory and practical software engineering.

Download this book as PDF

Beta: This book is currently in beta and is still under active review. It may contain errors or incomplete sections. Report errors or issues — contributions are welcome via the GitHub repository.

This book grew out of a simple observation: most software engineers use algorithms and data structures every day, yet many feel uncertain about the fundamentals. They may use a hash map or call a sorting function without fully understanding the guarantees those abstractions provide, or they may struggle when a problem requires designing a new algorithm from scratch. At the same time, Computer Science students often encounter algorithms in a highly theoretical setting that can feel disconnected from the code they write in practice.

Algorithms with TypeScript bridges that gap. It presents the core algorithms and data structures from a typical undergraduate algorithms curriculum - roughly equivalent to MIT's 6.006 and 6.046 - but uses TypeScript as the language of expression. Every algorithm discussed in the text is implemented, tested, and available in the accompanying repository. The implementations are not pseudocode translated into TypeScript; they are idiomatic, type-safe, and tested with a modern toolchain.

Who this book is for

This book is written for two audiences:

• Software engineers who want to solidify their understanding of algorithms and data structures. Perhaps you learned this material years ago and want a refresher, or perhaps you are self-taught and want to fill in the gaps. Either way, seeing algorithms in a language you likely use at work - TypeScript - makes the material immediately applicable.

• Computer Science students who are taking (or preparing to take) an algorithms course. The book follows a standard curricular sequence and includes exercises at the end of every chapter. The TypeScript implementations let you run, modify, and experiment with every algorithm.

Prerequisites

The book assumes you can read and write basic TypeScript or JavaScript. You should be comfortable with functions, loops, conditionals, arrays, and objects. No prior knowledge of algorithms or data structures is required - we build everything from the ground up, starting with the definition of an algorithm in Chapter 1.

Some chapters use mathematical notation, particularly for complexity analysis. Chapter 2 introduces asymptotic notation ($O$, $\Omega$, $\Theta$), and the Notation section that follows this preface summarizes all conventions used in the book. A comfort with basic algebra and mathematical reasoning is helpful but not strictly required; we explain each concept as it arises.

How to use this book

The book is organized into six parts:

• Part I: Foundations (Chapters 1-3) introduces the notion of an algorithm, the mathematical tools for analyzing algorithms, and recursion with divide-and-conquer.
• Part II: Sorting and Selection (Chapters 4-6) covers the classical sorting algorithms, from elementary $O(n^2)$ methods through $O(n\log n)$ comparison sorts to linear-time non-comparison sorts and selection algorithms.
• Part III: Data Structures (Chapters 7-11) presents the fundamental data structures: arrays, linked lists, stacks, queues, hash tables, trees, balanced search trees, heaps, and priority queues.
• Part IV: Graph Algorithms (Chapters 12-15) covers graph representations, traversal, shortest paths, minimum spanning trees, and network flow.
• Part V: Algorithm Design Techniques (Chapters 16--17) explores dynamic programming and greedy algorithms as general problem-solving strategies.
• Part VI: Advanced Topics (Chapters 18-22) covers disjoint sets, tries, string matching, computational complexity, and approximation algorithms.

The parts are designed to be read in order, as later chapters build on concepts and data structures introduced in earlier ones. Within each part, the chapters are largely self-contained - if you are comfortable with the prerequisites, you can often read individual chapters independently.

Each chapter follows a consistent structure: a motivating introduction, formal definitions, detailed algorithm descriptions with step-by-step traces, TypeScript implementations with code snippets, complexity analysis, and exercises. The exercises range from straightforward checks of understanding to more challenging problems that extend the material.

The code

All implementations live in the src/ directory of the repository, organized by chapter. Tests are in the tests/ directory with a parallel structure. To run the full test suite:

npm install
npm test

The code is written in TypeScript 5 with strict mode enabled, uses ES modules, and is tested with Vitest. See the project README for detailed setup instructions.

We encourage you to read the code alongside the text. The implementations are designed to be clear and readable rather than maximally optimized. Where there is a tension between clarity and performance, we choose clarity and discuss the performance implications in the text.

Acknowledgments

This book draws inspiration from several excellent texts, most notably Cormen, Leiserson, Rivest, and Stein's Introduction to Algorithms (CLRS), Sedgewick and Wayne's Algorithms, Niklaus Wirth's Algorithms + Data Structures = Programs, and Kleinberg and Tardos's Algorithm Design. The MIT OpenCourseWare materials for 6.006 and 6.046 were invaluable in shaping the curriculum. Full references are in the Bibliography.

Notation

This section summarizes the mathematical and typographical conventions used throughout the book. It is intended as a reference; each symbol is introduced and explained in context when it first appears.

Asymptotic notation

The asymptotic families correspond loosely to the comparison operators: $O$ to $\le$, $\Omega$ to $\ge$, $\Theta$ to $=$, $o$ to $<$, and $\omega$ to $>$.

Common growth rates

General mathematical notation

Logic and quantifiers

Set notation

Graph notation

Vertices are typically denoted by lowercase letters: $u$, $v$, $s$ (source), $t$ (sink). We use $s⇝v$ to denote a path from $s$ to $v$.

Probability notation

Complexity classes

Complexity classes are set in bold: $\mathbf{P}$, $\mathbf{NP}$, $\mathbf{co}\text{-}\mathbf{NP}$. NP-complete problems are written in small capitals in running text (e.g., SUBSET SUM, SAT, HAMILTONIAN CYCLE).

Algorithm and function names

In mathematical expressions, algorithm names are typeset in roman (upright) text to distinguish them from variables:

• $\text{parent}(i)$, $\text{left}(i)$, $\text{right}(i)$ for heap index calculations
• $\text{Relax}(u,v,w)$ for shortest-path edge relaxation
• $\text{OPT}(I)$ for the optimal solution value on instance $I$

Running-time recurrences use $T(n)$. Fibonacci numbers are $F(n)$.

Array and indexing conventions

All TypeScript implementations use 0-based indexing: the first element of an array arr is arr[0], and an array of $n$ elements has indices $0,1,\dots ,n-1$.

In mathematical discussion, array ranges are written as $A[\ell ..r)$ to denote the subarray from index $\ell$ (inclusive) to $r$ (exclusive). In heap formulas:

$$\text{parent}(i)=\lfloor (i-1)/2\rfloor ,\text{left}(i)=2i+1,\text{right}(i)=2i+2$$

Formal structures

Formal definitions, theorems, and lemmas are set in blockquotes with a label:

Definition X.Y --- Title

Statement of the definition.

Proofs end with the symbol $\square$. Examples are labeled Example X.Y and numbered within each chapter.

Code conventions

• All code is TypeScript with strict mode and ES module syntax.
• Generic type parameters (e.g., T, K, V) follow standard TypeScript conventions.
• The shared type Comparator<T> is (a: T, b: T) => number, returning negative if $a<b$, zero if $a=b$, and positive if $a>b$.
• Code snippets in chapters match the tested implementations in the src/ directory.

Introduction to Algorithms

In this chapter we discuss what an algorithm is, how algorithms can be expressed, and why studying them matters. We introduce TypeScript as the language used throughout the book, walk through setting up a development environment, and examine our first two algorithms in detail: finding the maximum of an array and the Sieve of Eratosthenes.

What is an algorithm?

Let us start with a discussion of what an algorithm is. Intuitively the notion is more or less clear: we are talking about some formal way to describe a computational procedure. According to the Merriam-Webster dictionary, an algorithm is "a set of steps that are followed in order to solve a mathematical problem or to complete a computer process".

Still, this is probably not formal enough. How do we choose the next step from the set of steps? Should the procedure stop eventually? What is the result of executing an algorithm? Many formal definitions of what constitutes an algorithm can be given; however, we will use the following working definition.

Definition 1.1 - Algorithm

A set of computational steps that specifies a formal computational procedure and has the following properties:

1. After each step is completed, the next step is unambiguously defined, or the algorithm stops its execution if there are no more steps left.

2. It is defined on a set of inputs and for each valid input it stops after a finite number of steps.

3. When it stops it produces a result, which we call its output.

4. Its steps and their order of execution can be formally and unambiguously specified using some language or notation.

These four properties capture the essence of what makes a procedure an algorithm. Let us look at each one briefly:

• Determinism (property 1): at every point during execution, there is exactly one thing to do next, or the algorithm is done. The next step is always uniquely determined by the current state.
• Termination (property 2): for every valid input, the algorithm eventually finishes. It does not run forever.
• Output (property 3): when the algorithm finishes, it produces a well-defined result.
• Formal specification (property 4): the algorithm can be written down precisely enough that it could, in principle, be carried out mechanically.

Expressing algorithms

Algorithms can be expressed in a variety of ways. We can even specify the execution steps using ordinary human language. Let us provide a few simple examples. A trivial first example is multiplying two numbers.

Example 1.1: Integer multiplication.

Steps:

1. Given two integer numbers, multiply them and return the result.

All the properties from Definition 1.1 are satisfied. There is only one step; after this step the algorithm stops; the step is formally specified; all pairs of integer numbers are valid inputs; and a valid result will be produced for each of them. If we denote the algorithm for multiplication as $\text{mult}$, then, for example,

$$\text{mult}(2,5)=10$$

and we can specify the algorithm more concisely as

$$\text{mult}(x,y)=x\times y$$

So far, while talking about algorithms, we have encountered no TypeScript or any other programming language notation. This is quite intentional: the notion of an algorithm is mathematical and abstract. Of course we can express any algorithm using TypeScript, but that will be just one of the possible formal representations - in this case, one that is also executable by a computer.

A careful reader might be puzzled by our confidence. How can we assert that any algorithm can be expressed using TypeScript? Can this claim be proven, given our definition? Is TypeScript powerful enough to express every possible algorithm? It turns out that it is. This can be proven rigorously: TypeScript (like most general-purpose programming languages) is Turing complete, meaning it can simulate any computation that a Turing machine can perform. Since Turing machines capture the full power of algorithmic computation, any algorithm can be expressed in TypeScript.

Let us look again at Definition 1.1. It states that we should be able to specify the computational procedure formally. It is now clear why we require this property: given a formal language such as TypeScript, we can specify the algorithm of interest and execute the specification on a computer. For the multiplication algorithm we can write:

function mult(x: number, y: number): number {
  return x * y;
}

The TypeScript specification is more concise and unambiguous than the natural-language version. Throughout the book we will primarily use TypeScript, but keep in mind that the algorithms we discuss can be expressed in other formal notations as well. Many Computer Science textbooks go as far as inventing their own pseudocode to avoid being tied to a particular programming language. We will not go that far and will happily use TypeScript - hence the name of the book, Algorithms with TypeScript.

Computational procedures that are not algorithms

Can we write a computational procedure that is not an algorithm? Yes. Consider the following TypeScript function:

function getMaximumNumber(): number {
  let x = 0;
  while (true) {
    x++;
  }
  return x;
}

This function never terminates: the while (true) loop runs forever, so the return statement is never reached. Property 2 of Definition 1.1 is violated - the procedure does not stop after a finite number of steps. This is therefore not an algorithm.

Another example of a non-algorithm is a division function defined on all pairs of numbers:

function divide(x: number, y: number): number {
  if (y === 0) {
    throw new Error('Cannot divide by zero');
  }
  return x / y;
}

This is not an algorithm according to our definition because the result is not defined for all inputs - when $y=0$ the procedure throws an error instead of producing an output (property 3 is violated). However, it is easy to fix this:

function divide(x: number, y: number): number {
  return y === 0 ? Infinity : x / y;
}

In fact, in JavaScript (and TypeScript), dividing by zero returns Infinity by default, so we could simply write:

function divide(x: number, y: number): number {
  return x / y;
}

This is an algorithm - but only because of JavaScript's particular treatment of division by zero.

From these examples we see that not every computational procedure that can be formally expressed is an algorithm. The properties in Definition 1.1 are genuine constraints.

Why study algorithms?

Before we proceed to our first nontrivial examples, let's briefly discuss why studying algorithms is worthwhile.

Correctness. Real-world software often needs to solve well-defined computational problems: sort a list, find the shortest route, compress data, search a database. An algorithm gives us a proven solution to such a problem. Understanding the classic algorithms means you can recognize when a problem you face has already been solved - and solved well.

Efficiency. Two algorithms that solve the same problem can differ enormously in how long they take or how much memory they use. Later in this book we will see sorting algorithms that take time proportional to $n^2$ (where $n$ is the number of elements) and others that take time proportional to $n\log n$. For a million elements, that is the difference between a trillion operations and roughly twenty million - a factor of 50,000. Choosing the right algorithm can be the difference between a program that finishes in seconds and one that takes hours.

Foundation for deeper topics. Algorithms and data structures form the backbone of Computer Science. Topics like databases, compilers, operating systems, machine learning, and cryptography all build on the ideas we will develop in this book.

Problem-solving skills. Even when you are not directly implementing a classic algorithm, the techniques you learn - divide and conquer, dynamic programming, greedy strategies, graph modeling - give you a powerful toolkit for approaching new problems.

Introduction to TypeScript

Throughout this book we use TypeScript as our implementation language. TypeScript is a statically typed superset of JavaScript: every valid JavaScript program is also a valid TypeScript program, but TypeScript adds optional type annotations that are checked at compile time.

We chose TypeScript for several reasons:

• Readability. TypeScript syntax is familiar to anyone who has worked with JavaScript, Java, C#, or similar C-family languages. Type annotations make function signatures self-documenting.
• Type safety. Generic types let us write algorithms that work with any element type while the compiler catches type errors before we run the code.
• Ubiquity. TypeScript runs anywhere JavaScript runs: in the browser, on the server (Node.js), and in countless tools. There is no special runtime to install beyond Node.js.
• Modern features. Destructuring, iterators, generator functions, and first-class functions make algorithm implementations concise and expressive.

Here is a small example that illustrates some features we will use frequently:

// A generic function that returns the first element of a non-empty array
function first<T>(arr: T[]): T {
  if (arr.length === 0) {
    throw new Error('Array must not be empty');
  }
  return arr[0];
}

const name: string = first(['Alice', 'Bob', 'Charlie']); // 'Alice'
const value: number = first([42, 17, 8]);                 // 42

The <T> syntax introduces a type parameter: the function works with arrays of any element type, and the compiler ensures that the return type matches the array's element type. We will use generics extensively when implementing data structures and sorting algorithms.

Setting up the development environment

To follow along with the code in this book, you will need:

1. Node.js (version 18 or later): download from https://nodejs.org or use a version manager such as nvm.
2. A text editor with TypeScript support. Visual Studio Code works particularly well, but any modern editor will do.

Once Node.js is installed, clone the book's repository and install the dependencies:

git clone https://github.com/amoilanen/Algorithms-with-Typescript.git
cd Algorithms-with-Typescript
npm install

The project uses the following tools, all installed automatically by npm install:

Useful commands:

npm test            # Run all tests
npm run test:watch  # Re-run tests on file changes
npm run typecheck   # Check types without emitting files
npm run lint        # Run the linter

Every algorithm in this book has a corresponding test suite. We encourage you to run the tests, read them, and experiment by modifying the implementations.

Finding the maximum element

Now that we are finished with definitions and setup, let's look at a few more interesting algorithms. The first problem is simple: given an array of numbers, find the largest one.

The problem

Input: An array $A$ of $n$ numbers $A[0],A[1],\dots ,A[n-1]$.

Output: The maximum value in $A$, or undefined if $A$ is empty.

A linear scan

The most natural approach is to scan through the array from left to right, keeping track of the largest value seen so far:

1. Set $\text{result}$ to undefined.
2. For each element $e$ in $A$:
   • If $\text{result}$ is undefined or $e>\text{result}$, set $\text{result}=e$.
3. Return $\text{result}$.

Here is the TypeScript implementation:

export function max(elements: number[]): number | undefined {
  let result: number | undefined;

  for (const element of elements) {
    if (result === undefined || element > result) {
      result = element;
    }
  }
  return result;
}

Let us trace through an example. Suppose $A=[2,1,4,2,3]$:

The function returns 4, which is indeed the maximum.

Correctness

We can argue correctness using a loop invariant: at the start of each iteration, result holds the maximum of all elements examined so far (or undefined if none have been examined).

• Initialization: Before the first iteration, no elements have been examined and result is undefined. The invariant holds trivially.
• Maintenance: Suppose the invariant holds at the start of an iteration. If the current element is greater than result (or result is undefined), we update result to element. Otherwise result already holds the maximum. In either case, after the iteration result is the maximum of all elements seen so far.
• Termination: The loop ends when all elements have been examined. By the invariant, result holds the maximum of the entire array.

Complexity analysis

The function performs one comparison per element and visits each element exactly once.

• Time complexity: $O(n)$, where $n$ is the length of the array.
• Space complexity: $O(1)$ - we use only a single variable result beyond the input.

Can we do better than $O(n)$? No. Any algorithm that finds the maximum must examine every element at least once: if it skipped an element, that element could have been the maximum. Therefore $O(n)$ is optimal for this problem.

Finding prime numbers: the Sieve of Eratosthenes

Our second algorithm is more substantial and has a rich history dating back over two thousand years. The goal is to find all prime numbers up to a given number $n$.

The problem

Input: A positive integer $n$.

Output: A list of all prime numbers $p$ such that $2\le p\le n$.

Recall that a prime number is an integer greater than 1 whose only positive divisors are 1 and itself. The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, ...

A naive approach: trial division

The most straightforward method is to test each number from 2 to $n$ for primality by checking whether it has any divisors other than 1 and itself:

export function primesUpToSlow(number: number): number[] {
  const primes: number[] = [];

  for (let current = 2; current <= number; current++) {
    if (isPrime(current)) {
      primes.push(current);
    }
  }
  return primes;
}

function isPrime(number: number): boolean {
  for (let i = 2; i < number; i++) {
    if (number % i === 0) {
      return false;
    }
  }
  return true;
}

For each candidate number $k$, the isPrime function tests all potential divisors from 2 up to $k-1$. If any of them divides $k$ evenly, $k$ is not prime.

This works, but it is slow. For each of the $n-1$ candidates, we may test up to $k-2$ divisors. In the worst case (when $k$ is prime), the isPrime check does $O(k)$ work. Summing over all candidates gives roughly $O(n^2)$ time. (We could improve isPrime by only testing up to $\sqrt{k}$, which brings the total to approximately $O(n\sqrt{n})$, but there is a fundamentally better approach.)

The Sieve of Eratosthenes

The Sieve of Eratosthenes, attributed to the ancient Greek mathematician Eratosthenes of Cyrene (c. 276--194 BC), takes a different approach. Instead of testing each number individually, it starts by assuming all numbers are prime and then systematically eliminates the ones that are not:

1. Create a boolean array isPrime[2..n], initially all true.
2. For each number $p$ starting from 2:
   • If isPrime[p] is true, then $p$ is prime. Mark all multiples of $p$ (starting from $2p$) as false.
3. Collect all indices that remain true.

Here is the TypeScript implementation:

export function primesUpTo(number: number): number[] {
  const isPrimeNumber: boolean[] = [];
  const primes: number[] = [];
  let current = 2;

  for (let i = 2; i <= number; i++) {
    isPrimeNumber[i] = true;
  }

  while (current <= number) {
    if (isPrimeNumber[current]) {
      primes.push(current);
      for (let j = 2 * current; j <= number; j += current) {
        isPrimeNumber[j] = false;
      }
    }
    current++;
  }
  return primes;
}

Tracing through an example

Let us trace the sieve for $n=20$. We start with all numbers from 2 to 20 marked as potentially prime:

 2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
 T  T  T  T  T  T  T  T  T  T  T  T  T  T  T  T  T  T  T

$p=2$: 2 is prime. Cross out multiples of 2: 4, 6, 8, 10, 12, 14, 16, 18, 20.

 2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
 T  T  F  T  F  T  F  T  F  T  F  T  F  T  F  T  F  T  F

$p=3$: 3 is still marked true, so it is prime. Cross out multiples of 3: 6, 9, 12, 15, 18 (some are already crossed out).

 2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
 T  T  F  T  F  T  F  F  F  T  F  T  F  F  F  T  F  T  F

$p=4$: 4 is marked false (not prime). Skip it.

$p=5$: 5 is marked true, so it is prime. Cross out multiples of 5: 10, 15, 20 (all already crossed out). The array is unchanged.

$p=6$: 6 is marked false (not prime). Skip it.

$p=7$: 7 is marked true, so it is prime. Its first multiple is 14, which is already crossed out. The array is unchanged.

$p=8,9,10$: All marked false. Skip.

$p=11$: 11 is marked true, so it is prime. Its first multiple within range would be 22, which exceeds $n=20$. No crossings.

$p=12$: Marked false. Skip.

$p=13$: 13 is marked true, so it is prime. Its first multiple within range would be 26, which exceeds $n=20$. No crossings.

$p=14,15,16$: All marked false. Skip.

$p=17$: 17 is marked true, so it is prime. Its first multiple within range would be 34, which exceeds $n=20$. No crossings.

$p=18$: Marked false. Skip.

$p=19$: 19 is marked true, so it is prime. Its first multiple within range would be 38, which exceeds $n=20$. No crossings.

$p=20$: Marked false. Skip.

The final state of the array is:

 2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
 T  T  F  T  F  T  F  F  F  T  F  T  F  F  F  T  F  T  F

The numbers that remain true are:

$$2,3,5,7,11,13,17,19$$

These are exactly the primes up to 20.

Why does the sieve work?

The key insight is: if a number $k$ is composite (not prime), then $k=a\times b$ for some integers $a,b$ with $2\le a\le b<k$. The smallest such factor $a$ is itself prime (otherwise it could be factored further). When the sieve processes $p=a$, it marks $k=a\times b$ as composite. Therefore, every composite number gets marked false by the time the sieve finishes.

Conversely, if a number $k$ is prime, no smaller prime $p$ divides it, so $k$ is never marked false. The sieve correctly identifies exactly the prime numbers.

Complexity analysis

How much work does the sieve do? For each prime $p\le n$, it crosses out at most $n/p$ multiples. The total work is proportional to:

$$\sum _{p\text{ prime},p\le n}\frac{n}{p}=n\sum _{p\text{ prime},p\le n}\frac{1}{p}$$

A classical result in number theory states that the sum of the reciprocals of the primes up to $n$ grows as $\ln (\ln (n))$. Therefore:

• Time complexity: $O(n\ln (\ln n))$.
• Space complexity: $O(n)$ for the boolean array.

Note: since $\ln n$ and ${\log }_{2}n$ differ only by a constant factor (${\log }_{2}n=\ln n/\ln 2$), it does not matter which logarithm base we use inside big-$O$ notation. You may see this complexity written equivalently as $O(n\log \log n)$ in other sources.

Compare this with the naive trial-division approach at $O(n\sqrt{n})$. For $n=1,000,000$:

The sieve is roughly 300 times faster - an enormous difference for large inputs.

Comparing the two approaches

This is our first encounter with a recurring theme in this book: different algorithms for the same problem can have vastly different performance characteristics. The naive approach is simple and easy to understand, but the sieve achieves dramatically better performance by exploiting the structure of the problem.

Throughout the book, we will develop the tools to analyze these differences precisely. In Chapter 2 we formalize the notion of time complexity using asymptotic notation ($O$, $\Omega$, $\Theta$), which gives us a language for comparing algorithms independently of the specific hardware they run on.

Summary

In this chapter we defined what an algorithm is, introduced TypeScript as our implementation language, and studied two concrete algorithms. We saw that:

• An algorithm is a well-defined computational procedure that terminates on all valid inputs and produces a result.
• Algorithms can be expressed in many notations; we use TypeScript because it combines readability, type safety, and executability.
• Even for simple problems, the choice of algorithm can dramatically affect performance: the Sieve of Eratosthenes outperforms trial division by orders of magnitude.

In the next chapter, we develop the mathematical framework - asymptotic notation and complexity analysis - that lets us reason precisely about algorithm efficiency. These tools will be essential throughout the rest of the book.

Exercises

Exercise 1.1. Write a function min(elements: number[]): number | undefined that returns the minimum element of an array, analogous to the max function. What is its time complexity?

Exercise 1.2. The isPrime function in the trial-division approach tests divisors from 2 all the way up to $k-1$. Explain why it suffices to test only up to $\lfloor \sqrt{k}\rfloor$. Modify the function accordingly and analyze the improved time complexity for finding all primes up to $n$.

Exercise 1.3. The Sieve of Eratosthenes as presented starts crossing out multiples of $p$ from $2p$. Show that it is sufficient to start from $p^2$ instead. Why does this not change the asymptotic time complexity?

Exercise 1.4. The proper divisors of a positive integer $n$ are all positive divisors of $n$ other than $n$ itself. For example, the proper divisors of 12 are 1, 2, 3, 4, and 6. A perfect number is a positive integer that equals the sum of its proper divisors (e.g., $6=1+2+3$). Write a function isPerfect(n: number): boolean and use it to find all perfect numbers up to 10,000. What is the time complexity of your approach?

Exercise 1.5. Consider the following function:

function mystery(n: number): number {
  if (n <= 1) return n;
  return mystery(n - 1) + mystery(n - 2);
}

Does this function define an algorithm according to Definition 1.1? What does it compute? Try calling it with $n=5$, $n=10$, and $n=40$. What do you observe about the running time? (We will revisit this function in Chapter 16 on dynamic programming.)

Analyzing Algorithms

In Chapter 1 we saw that two algorithms for the same problem — trial division versus the Sieve of Eratosthenes — can differ enormously in performance. In this chapter we develop the mathematical framework for making such comparisons precise. We introduce asymptotic notation, which lets us describe how an algorithm's resource usage grows with input size, and we study several techniques for analyzing running time: best-, worst-, and average-case analysis, amortized analysis, and recurrence relations.

Why analyze algorithms?

Suppose you have two sorting algorithms, $A$ and $B$, and you want to know which one is faster. The most direct approach is to run both on the same input and measure the wall-clock time. This is called benchmarking, and it has an important place in software engineering. However, benchmarking has limitations:

• Hardware dependence. Algorithm $A$ might be faster on your laptop but slower on a different machine with a different CPU, cache hierarchy, or memory bandwidth.
• Input dependence. Algorithm $A$ might be faster on the particular test data you chose, but slower on inputs that arise in practice.
• Implementation effects. A clever implementation of a theoretically slower algorithm can outperform a naive implementation of a theoretically faster one.

What we want is a way to compare algorithms independently of these factors — a way to reason about the inherent efficiency of an algorithm rather than the efficiency of a particular implementation on a particular machine with a particular input. This is what asymptotic analysis provides.

The idea is to count the number of "basic operations" an algorithm performs as a function of the input size $n$, and then focus on how that function grows as $n$ becomes large. We ignore constant factors (which depend on the hardware and implementation) and lower-order terms (which become negligible for large $n$). The result is a concise characterization of an algorithm's scalability.

Measuring input size and running time

Before we can analyze an algorithm, we need to agree on two things: what counts as the input size, and what counts as a basic operation.

Input size is usually the most natural measure of how much data the algorithm must process:

• For an array of numbers, the input size is the number of elements $n$.
• For a graph, the input size is often specified as a pair $(V,E)$ — the number of vertices and edges.
• For a number-theoretic algorithm like the Sieve of Eratosthenes, the input size is the number $n$ itself.

Basic operations are the elementary steps we count. Common choices include comparisons, arithmetic operations, assignments, or array accesses. The specific choice rarely matters for asymptotic analysis, because changing which operation we count changes the total by at most a constant factor.

Definition 2.1 - Running time

The running time of an algorithm on a given input is the number of basic operations it performs when executed on that input.

We are usually interested in expressing the running time as a function $T(n)$ of the input size $n$.

Example 2.1: Running time of max.

Recall the max function from Chapter 1:

export function max(elements: number[]): number | undefined {
  let result: number | undefined;

  for (const element of elements) {
    if (result === undefined || element > result) {
      result = element;
    }
  }
  return result;
}

If we count comparisons as our basic operation, the loop performs exactly one comparison per element (the element > result check; the undefined check is bookkeeping). For an array of $n$ elements, the running time is $T(n)=n$.

Asymptotic notation

Rather than stating that an algorithm takes exactly $3n^2+7n+4$ operations, we want to capture the growth rate — the fact that the dominant behavior is quadratic. Asymptotic notation gives us a precise way to do this.

Big-O: upper bounds

Definition 2.2 - Big-O notation

Let $f(n)$ and $g(n)$ be functions from the non-negative integers to the non-negative reals. We write

$$f(n)=O(g(n))$$

if there exist constants $c>0$ and $n_0\ge 0$ such that

$$f(n)\le c\cdot g(n)\text{for all }n\ge n_0.$$

In words: $f$ grows no faster than $g$, up to a constant factor, for sufficiently large $n$.

Example 2.2. Let $f(n)=3n^2+7n+4$. We claim $f(n)=O(n^2)$.

Proof. For $n\ge 1$, we have $7n\le 7n^2$ and $4\le 4n^2$, so

$$f(n)=3n^2+7n+4\le 3n^2+7n^2+4n^2=14n^2.$$

Choosing $c=14$ and $n_0=1$ satisfies Definition 2.2. $\square$

Note that $f(n)=O(n^3)$ is also technically true — $n^2$ is bounded above by $n^3$ — but it is less informative. By convention, we try to state the tightest bound we can prove.

Big-Omega: lower bounds

Definition 2.3 - Big-Omega notation

We write $f(n)=\Omega (g(n))$ if there exist constants $c>0$ and $n_0\ge 0$ such that

$$f(n)\ge c\cdot g(n)\text{for all }n\ge n_0.$$

In words: $f$ grows at least as fast as $g$, up to a constant factor.

Example 2.3. $3n^2+7n+4=\Omega (n^2)$.

Proof. For all $n\ge 0$, $3n^2+7n+4\ge 3n^2\ge 3\cdot n^2$. Choose $c=3$ and $n_0=0$. $\square$

Big-Omega is especially useful for expressing lower bounds on problems: "any algorithm that solves this problem must take at least $\Omega (g(n))$ time."

Big-Theta: tight bounds

Definition 2.4 - Big-Theta notation

We write $f(n)=\Theta (g(n))$ if $f(n)=O(g(n))$ and $f(n)=\Omega (g(n))$.

Equivalently, there exist constants $c_1,c_2>0$ and $n_0\ge 0$ such that

$$c_1\cdot g(n)\le f(n)\le c_2\cdot g(n)\text{for all }n\ge n_0.$$

In words: $f$ and $g$ grow at the same rate, up to constant factors.

Example 2.4. From Examples 2.2 and 2.3, we have $3n^2+7n+4=\Theta (n^2)$.

Big-Theta is the most precise statement: it says the function grows exactly like $g(n)$, within constant factors. When we can determine a Big-Theta bound for an algorithm, we have characterized its running time completely (in the asymptotic sense).

Summary of notation

The analogy to $\le$, $\ge$, $=$ is informal but helpful for intuition. Formally, all three notations suppress constant factors and describe behavior only for sufficiently large $n$.

Common growth rates

The following table lists growth rates that appear throughout this book, ordered from slowest to fastest:

To appreciate the practical impact, consider an algorithm that performs $T(n)$ operations on a computer executing $10^9$ operations per second:

The table makes a powerful point: the gap between $O(n\log n)$ and $O(n^2)$ is large for a million elements, and the jump to $O(2^n)$ is catastrophic even for modest inputs.

Best case, worst case, and average case

The running time of an algorithm usually depends on the specific input, not just its size. Consider insertion sort.

Insertion sort as a running example

The following is an implementation of insertion sort, which we will study fully in Chapter 4. For now, we use it as an analysis example:

export function insertionSort<T>(
  elements: T[],
  comparator: Comparator<T> = numberComparator as Comparator<T>,
): T[] {
  const copy = elements.slice(0);

  for (let i = 1; i < copy.length; i++) {
    const toInsert = copy[i]!;
    let insertIndex = i - 1;

    while (insertIndex >= 0 && comparator(toInsert, copy[insertIndex]!) < 0) {
      copy[insertIndex + 1] = copy[insertIndex]!;
      insertIndex--;
    }
    insertIndex++;
    copy[insertIndex] = toInsert;
  }
  return copy;
}

The outer loop runs $n-1$ iterations (for $i=1,2,\dots ,n-1$). For each iteration, the inner while loop shifts elements to the right until it finds the correct insertion point. The number of shifts depends on the input.

Worst-case analysis

Definition 2.5 - Worst-case running time

The worst-case running time $T_{\text{worst}}(n)$ is the maximum running time over all inputs of size $n$:

$$T_{\text{worst}}(n)=\underset{\text{inputs }I\text{ of size }n}{\max }T(I).$$

For insertion sort, the worst case occurs when the array is sorted in reverse order: $[n,n-1,\dots ,2,1]$. In this case, every new element must be shifted past all previously sorted elements. The inner loop performs $i$ comparisons in iteration $i$, so the total number of comparisons is:

$$\sum _{i=1}^{n-1}i=\frac{n(n-1)}{2}=\Theta (n^2).$$

Best-case analysis

Definition 2.6 - Best-case running time

The best-case running time $T_{\text{best}}(n)$ is the minimum running time over all inputs of size $n$:

$$T_{\text{best}}(n)=\underset{\text{inputs }I\text{ of size }n}{\min }T(I).$$

For insertion sort, the best case occurs when the array is already sorted. Each new element is already in its correct position, so the inner loop performs zero shifts — just one comparison to discover that no shifting is needed. The total is:

$$\sum _{i=1}^{n-1}1=n-1=\Theta (n).$$

This is remarkable: insertion sort runs in linear time on already-sorted input, matching the theoretical minimum for any comparison-based algorithm that must verify sortedness.

Average-case analysis

Definition 2.7 - Average-case running time

The average-case running time is the expected running time over some distribution of inputs. For a uniform distribution over all permutations of $n$ elements:

$$T_{\text{avg}}(n)=\frac{1}{n!}\sum _{\text{permutations }\pi }T(\pi ).$$

For insertion sort, consider iteration $i$: the element being inserted has an equal probability of belonging at any of the $i+1$ positions in the sorted prefix. On average, it must be shifted past half of the sorted elements, so the expected number of comparisons in iteration $i$ is roughly $i/2$. The total expected comparisons are:

$$\sum _{i=1}^{n-1}\frac{i}{2}=\frac{n(n-1)}{4}=\Theta (n^2).$$

The average case is still $\Theta (n^2)$ — the same order of growth as the worst case. The constant factor is half as large, but asymptotically the behavior is the same.

Which case matters?

In practice, worst-case analysis is the most commonly used, for several reasons:

1. Guarantees. The worst case gives an upper bound that holds for every input. This is crucial in real-time systems, web servers, and other contexts where performance must be predictable.
2. Average case can be misleading. The "average" depends on the input distribution, which we may not know. If the actual inputs differ from our assumption, the average-case analysis may not apply.
3. Worst case is often typical. For many algorithms, the worst case and average case have the same asymptotic growth rate (as we just saw with insertion sort).

We will occasionally discuss best-case and average-case bounds when they provide useful insight, but unless otherwise stated, all complexity bounds in this book refer to the worst case.

Amortized analysis

Sometimes an operation is expensive occasionally but cheap most of the time. Amortized analysis gives us a way to average the cost over a sequence of operations, providing a tighter bound than the worst-case cost per operation.

The dynamic array example

Consider a dynamic array (like JavaScript's Array or std::vector in C++) that supports an append operation. The array maintains an internal buffer of some capacity. When the buffer is full and a new element is appended, the array allocates a new buffer of double the capacity and copies all existing elements over. This resize operation costs $O(n)$, where $n$ is the current number of elements.

At first glance, this seems concerning: a single append can cost $O(n)$. But resizes happen infrequently — only when the size reaches a power of 2. Let us analyze the cost of $n$ consecutive appends starting from an empty array.

The resize operations happen at sizes 1, 2, 4, 8, $\dots$, $2^k$, where $2^k\le n$. The total copying cost across all resizes is:

$$1+2+4+8+\cdots +2^k=2^{k+1}-1<2n.$$

Adding the $n$ operations that simply write the new element into the array (cost 1 each), the total cost of $n$ appends is less than $3n$. Therefore the amortized cost per append is:

$$\frac{3n}{n}=O(1).$$

Each individual append may cost $O(n)$ in the worst case, but averaged over a sequence of operations, the cost is $O(1)$ per operation.

Amortized vs. average case

It is important to distinguish amortized analysis from average-case analysis:

• Average case averages over random inputs: we assume a probability distribution on the inputs and compute the expected running time.
• Amortized analysis averages over a sequence of operations on a worst-case input: no probability is involved. The guarantee holds deterministically.

Amortized analysis says: "no matter what sequence of $n$ operations you perform, the total cost is at most $f(n)$, so the amortized cost per operation is $f(n)/n$." This is a worst-case guarantee about the total, not a probabilistic statement.

We will see amortized analysis again in Chapter 7 (dynamic arrays), Chapter 11 (binary heaps), and Chapter 18 (union-find).

Recurrence relations

When an algorithm solves a problem by breaking it into smaller instances of the same problem, its running time is naturally expressed as a recurrence relation: a formula that expresses $T(n)$ in terms of $T$ applied to smaller values.

Setting up a recurrence

Example 2.5: Binary search. Binary search (discussed in Chapter 3) repeatedly halves the search space:

1. Compare the target with the middle element.
2. If they match, return the index.
3. Otherwise, recurse on the left or right half.

The running time satisfies the recurrence:

$$T(n)=T(n/2)+O(1),T(1)=O(1).$$

The $T(n/2)$ term accounts for the recursive call on half the array, and the $O(1)$ term accounts for the comparison and index computation.

Example 2.6: Merge sort. Merge sort (discussed in Chapter 5) divides the array in half, recursively sorts both halves, and merges the results:

$$T(n)=2T(n/2)+O(n),T(1)=O(1).$$

The two recursive calls each process half the array ($2T(n/2)$), and the merge step takes $O(n)$ time.

Solving recurrences by expansion

One way to solve a recurrence is to expand it repeatedly until a pattern emerges.

Example 2.7: Solving the binary search recurrence.

$$T(n)=T(n/2)+c$$

Expanding:

$$T(n)=T(n/4)+c+c=T(n/4)+2c$$ $$=T(n/8)+3c$$ $$=T(n/2^k)+kc$$

The recursion bottoms out when $n/2^k=1$, i.e., $k={\log }_{2}n$. Therefore:

$$T(n)=T(1)+c{\log }_{2}n=O(\log n).$$

Example 2.8: Solving the merge sort recurrence.

$$T(n)=2T(n/2)+cn$$

Expanding:

$$T(n)=2[2T(n/4)+cn/2]+cn=4T(n/4)+2cn$$ $$=4[2T(n/8)+cn/4]+2cn=8T(n/8)+3cn$$

At level $k$: $T(n)=2^{k}T(n/2^k)+kcn$. Setting $k={\log }_{2}n$:

$$T(n)=nT(1)+cn{\log }_{2}n=O(n\log n).$$

The recursion tree method

A recursion tree is a visual tool for solving recurrences. Each node represents the cost at one level of recursion, and the total cost is the sum over all nodes.

For merge sort with $T(n)=2T(n/2)+cn$:

Level 0:              cn                    → cost cn
                    /    \
Level 1:        cn/2      cn/2              → cost cn
                / \       / \
Level 2:    cn/4  cn/4  cn/4  cn/4          → cost cn
              ...         ...
Level k:   c  c  c  ...  c  c  c            → cost cn
           (n leaves)

There are ${\log }_{2}n$ levels, each contributing $cn$ work, so the total is $cn{\log }_{2}n=O(n\log n)$.

The Master Theorem

The Master Theorem provides a general solution for recurrences of a common form.

Definition 2.8 - The Master Theorem

Let $a\ge 1$ and $b>1$ be constants, let $f(n)$ be a function, and let $T(n)$ be defined by the recurrence

$$T(n)=aT(n/b)+f(n).$$

Then $T(n)$ can be bounded asymptotically as follows:

1. If $f(n)=O(n^{{\log }_{b}a-ϵ})$ for some constant $ϵ>0$, then $T(n)=\Theta (n^{{\log }_{b}a})$.

2. If $f(n)=\Theta (n^{{\log }_{b}a})$, then $T(n)=\Theta (n^{{\log }_{b}a}\log n)$.

3. If $f(n)=\Omega (n^{{\log }_{b}a+ϵ})$ for some constant $ϵ>0$, and if $af(n/b)\le cf(n)$ for some constant $c<1$ and sufficiently large $n$, then $T(n)=\Theta (f(n))$.

The three cases correspond to three scenarios, and the intuition comes directly from examining the recursion tree for the general recurrence $T(n)=aT(n/b)+f(n)$.

A note to the reader. Understanding why the Master Theorem works is not required for the rest of this book — only knowing how to apply it (which we cover in the examples that follow). The proof sketch below is provided for the sake of completeness. If the math feels a bit daunting, feel free to skip ahead to Example 2.9 and return to this section later.

The general recursion tree

At each level of the recursion, one problem of size $m$ spawns $a$ subproblems of size $m/b$ and performs $f(m)$ non-recursive work. The following table summarizes the tree level by level:

The tree has ${\log }_{b}n$ levels (since we divide by $b$ at each step until we reach size 1). The number of leaves is $a^{{\log }_{b}n}=n^{{\log }_{b}a}$ — this quantity is central to all three cases.

Why does $a^{{\log }_{b}n}=n^{{\log }_{b}a}$?

This identity can look like a magic trick the first time you see it. Here is a concrete way to understand it, followed by the general argument.

Concrete example. Take $a=3$, $b=2$, $n=16$. Then ${\log }_{2}16=4$, so the left side is $3^4=81$. For the right side, ${\log }_{2}3\approx 1.585$, so $16^{1.585}=16^{{\log }_{2}3}\approx 81$. They match — but why?

Step-by-step derivation. The key idea is to rewrite $a$ as a power of $b$. Since logarithms and exponents are inverses, we can always write $a=b^{{\log }_{b}a}$. Now substitute this into $a^{{\log }_{b}n}$:

$$a^{{\log }_{b}n}={\left(b^{{\log }_{b}a}\right)}^{{\log }_{b}n}=b^{({\log }_{b}a)({\log }_{b}n)}.$$

Meanwhile, we can do the same thing with $n=b^{{\log }_{b}n}$ and compute:

$$n^{{\log }_{b}a}={\left(b^{{\log }_{b}n}\right)}^{{\log }_{b}a}=b^{({\log }_{b}n)({\log }_{b}a)}.$$

The two exponents are identical — just multiplication in different order — so $a^{{\log }_{b}n}=n^{{\log }_{b}a}$. The trick is nothing more than $(x^p{)}^q=(x^q{)}^p$.

Why it matters here. The left form, $a^{{\log }_{b}n}$, is easy to read off the tree: $a$ children per node, ${\log }_{b}n$ levels deep, so $a^{{\log }_{b}n}$ leaves. The right form, $n^{{\log }_{b}a}$, is more useful for asymptotic analysis because it expresses the leaf count as a polynomial in $n$, making it easy to compare with $f(n)$.

The total cost is the sum across all levels:

$$T(n)=\sum _{k=0}^{{\log }_{b}n}{a}^k\cdot f\left(\frac{n}{b^k}\right).$$

The Master Theorem's three cases arise from comparing the non-recursive work $f(n)$ to the leaf count $n^{{\log }_{b}a}$, which determines the shape of how work is distributed across levels.

Case 1: Leaf-dominated — $f(n)=O(n^{{\log }_{b}a-ϵ})$

When $f(n)$ is polynomially smaller than $n^{{\log }_{b}a}$, the work increases geometrically as you move down the tree. Each level does more work than the one above it, so the leaves dominate:

Since the bottom level dominates a geometric series, the total is $T(n)=\Theta (n^{{\log }_{b}a})$.

Intuition: The function $f(n)$ shrinks so fast that the proliferation of subproblems ($a$ new ones per level) outpaces the reduction in per-node work. The cost is essentially the number of leaves times $\Theta (1)$ per leaf.

Example: Strassen's algorithm, $T(n)=7T(n/2)+O(n^2)$. Here $n^{{\log }_{2}7}\approx n^{2.81}$, which dominates $f(n)=O(n^2)$.

Case 2: Evenly distributed — $f(n)=\Theta (n^{{\log }_{b}a})$

When $f(n)$ is proportional to $n^{{\log }_{b}a}$, a remarkable cancellation occurs: every level of the tree contributes roughly the same amount of work. The increase in the number of nodes at each level is exactly offset by the decrease in per-node work:

There are ${\log }_{b}n$ levels, each contributing $\Theta (n^{{\log }_{b}a})$, so $T(n)=\Theta (n^{{\log }_{b}a}\log n)$.

Intuition: To see why each level contributes the same work, note that at level $k$, the work is $a^k\cdot f(n/b^k)$. If $f(n)=\Theta (n^{{\log }_{b}a})$, then $f(n/b^k)=\Theta (n^{{\log }_{b}a}/b^{k{\log }_{b}a})=\Theta (n^{{\log }_{b}a}/a^k)$. Multiplying by $a^k$ gives $\Theta (n^{{\log }_{b}a})$ — the $a^k$ factors cancel exactly.

Example: Merge sort, $T(n)=2T(n/2)+O(n)$. Here $n^{{\log }_{2}2}=n=f(n)$, so every level costs $\Theta (n)$, and the total is $\Theta (n\log n)$.

Case 3: Root-dominated — $f(n)=\Omega (n^{{\log }_{b}a+ϵ})$

When $f(n)$ is polynomially larger than $n^{{\log }_{b}a}$, the work decreases geometrically as you move down the tree. The root does the most work, and each subsequent level does less:

The total is a decreasing geometric series dominated by its first term, so $T(n)=\Theta (f(n))$.

Intuition: The non-recursive work $f(n)$ is so large relative to the number of subproblems that the recursive calls barely contribute. The extra "regularity condition" $af(n/b)\le cf(n)$ for some $c<1$ guarantees that the per-level costs truly form a decreasing geometric series (i.e., that $f$ doesn't have pathological oscillations that could break the argument).

Example: $T(n)=T(n/2)+n$. Here $n^{{\log }_{2}1}=1$, but $f(n)=n$. The root does $n$ work, the next level does $n/2$, then $n/4$, and so on. The total is $n+n/2+n/4+\cdots <2n=\Theta (n)=\Theta (f(n))$.

Proof intuition: why these are the only three cases

The key insight is that the per-level work at level $k$ is:

$$W(k)=a^k\cdot f\left(\frac{n}{b^k}\right).$$

As $k$ increases from $0$ to ${\log }_{b}n$, the factor $a^k$ grows exponentially (more subproblems) while $f(n/b^k)$ shrinks (smaller subproblem sizes). The total cost is ${\sum }_{k}W(k)$, which is a sum of ${\log }_{b}n$ terms. The behavior of this sum depends on whether $W(k)$ is increasing, constant, or decreasing in $k$:

• If $f$ shrinks faster than $a^k$ grows → $W(k)$ increases → geometric sum dominated by the last term (leaves) → Case 1.
• If $f$ shrinks at exactly the rate $a^k$ grows → $W(k)$ is constant → ${\log }_{b}n$ equal terms → Case 2.
• If $f$ shrinks slower than $a^k$ grows → $W(k)$ decreases → geometric sum dominated by the first term (root) → Case 3.

The critical exponent ${\log }_{b}a$ is the dividing line: it is the rate at which the number of subproblems grows across levels. When $f(n)$ grows faster than $n^{{\log }_{b}a}$, the root dominates; when it grows slower, the leaves dominate; when it grows at the same rate, all levels are balanced.

Let us apply the Master Theorem to our earlier examples.

Example 2.9: Binary search. $T(n)=T(n/2)+O(1)$.

Here $a=1$, $b=2$, $f(n)=O(1)$. We have $n^{{\log }_{b}a}=n^{{\log }_{2}1}=n^0=1$. Since $f(n)=\Theta (1)=\Theta (n^{{\log }_{b}a})$, Case 2 applies:

$$T(n)=\Theta (\log n).$$

Example 2.10: Merge sort. $T(n)=2T(n/2)+O(n)$.

Here $a=2$, $b=2$, $f(n)=O(n)$. We have $n^{{\log }_{b}a}=n^{{\log }_{2}2}=n^1=n$. Since $f(n)=\Theta (n)=\Theta (n^{{\log }_{b}a})$, Case 2 applies:

$$T(n)=\Theta (n\log n).$$

Example 2.11: Strassen's matrix multiplication. $T(n)=7T(n/2)+O(n^2)$.

Here $a=7$, $b=2$, $f(n)=O(n^2)$. We have $n^{{\log }_{b}a}=n^{{\log }_{2}7}\approx n^{2.807}$. Since $f(n)=O(n^2)=O(n^{2.807-ϵ})$ with $ϵ\approx 0.807$, Case 1 applies:

$$T(n)=\Theta (n^{{\log }_{2}7})\approx \Theta (n^{2.807}).$$

This is better than the naive $O(n^3)$ matrix multiplication.

Limitations of the Master Theorem

The Master Theorem does not cover all recurrences. It requires that the subproblems be of equal size $n/b$ and that $f(n)$ fall into one of the three cases. Recurrences like $T(n)=T(n/3)+T(2n/3)+O(n)$ (which arises in randomized quicksort analysis) do not fit the template directly. For such cases, the recursion-tree method or the Akra–Bazzi theorem can be used.

Space complexity

So far we have focused on time complexity, but algorithms also consume memory. Space complexity measures the amount of additional memory an algorithm uses beyond the input.

Definition 2.9 - Space complexity

The space complexity of an algorithm is the maximum amount of memory it uses at any point during execution, measured as a function of the input size.

We distinguish between:

• Auxiliary space: the extra memory used beyond the input itself.
• Total space: auxiliary space plus the space for the input.

Unless stated otherwise, when we refer to "space complexity" in this book, we mean auxiliary space.

Example 2.12: Space complexity of max.

The max function from Chapter 1 uses a single variable result. Its auxiliary space is $O(1)$.

Example 2.13: Space complexity of merge sort.

Merge sort requires a temporary array of size $n$ for the merge step, plus $O(\log n)$ space for the recursion stack. Its auxiliary space is $O(n)$.

Example 2.14: Space complexity of insertion sort.

Our insertion sort implementation copies the input array (space $O(n)$). An in-place variant that sorts the array directly would use only $O(1)$ auxiliary space.

Time–space trade-offs

Often there is a trade-off between time and space. An algorithm can sometimes be made faster by using more memory, or made more memory-efficient at the cost of additional computation. A classic example:

• Hash table lookup (Chapter 8): $O(1)$ average time, $O(n)$ space.
• Linear search through an unsorted array: $O(n)$ time, $O(1)$ space.

Both solve the problem of finding an element in a collection, but they make different trade-offs. Recognizing and navigating these trade-offs is a recurring theme in algorithm design.

Practical considerations

Asymptotic analysis is a powerful framework, but it has limitations that a practicing programmer should keep in mind.

Constant factors matter for moderate $n$

Asymptotic notation hides constant factors. As an example, an algorithm with running time $100n$ is $O(n)$, and an algorithm with running time $2n\log n$ is $O(n\log n)$. For $n<2^{50}$, the "slower" $O(n\log n)$ algorithm is actually faster. In practice, constant factors depend on:

• The number of operations per step.
• Cache behavior — algorithms with good spatial locality are faster in practice.
• Branch prediction — algorithms with predictable control flow benefit from CPU branch predictors.

This is why, for example, insertion sort (which is $O(n^2)$) is often used for small arrays (say, $n<20$) even inside asymptotically faster algorithms like merge sort. The constant factor is smaller, and for tiny inputs the quadratic term has not yet become dominant.

Lower-order terms

An algorithm that performs $n^2+10^{6}n$ operations is $\Theta (n^2)$, but for $n<10^6$, the linear term dominates. Asymptotic analysis describes long-term growth; for small inputs, the actual constants and lower-order terms may be more important.

Choosing the right model

Our analysis assumes a simple model where every basic operation takes the same amount of time. Real computers have caches, pipelines, and memory hierarchies that make some access patterns much faster than others. An algorithm that accesses memory sequentially (like insertion sort) can be significantly faster in practice than one that accesses memory randomly (like binary search on a large array), even if the latter has a better asymptotic bound.

Despite these caveats, asymptotic analysis remains the single most useful tool for comparing algorithms. It correctly predicts which algorithm will win for large enough inputs, and "large enough" usually means "the sizes that actually matter in practice."

Summary

In this chapter we have developed the fundamental tools for analyzing algorithms:

• Asymptotic notation ($O$, $\Omega$, $\Theta$) captures growth rates while abstracting away constant factors and hardware details.
• Worst-case analysis gives reliable upper bounds on running time. Best-case and average-case analyses provide additional insight.
• Amortized analysis reveals that operations with occasional expensive steps can still be efficient on average.
• Recurrence relations express the running time of recursive algorithms, and the Master Theorem provides a quick way to solve common recurrences.
• Space complexity measures memory usage and highlights time–space trade-offs.

Armed with these tools, we are ready to analyze every algorithm in this book rigorously. In the next chapter, we explore recursion and the divide-and-conquer strategy — one of the most powerful algorithm design techniques — and apply our analytical framework to algorithms like binary search and the closest pair of points.

Exercises

Exercise 2.1. Rank the following functions by asymptotic growth rate, from slowest to fastest. For each consecutive pair, state whether $f=O(g)$, $f=\Omega (g)$, or $f=\Theta (g)$.

$${\log }_{2}n,n^2,\sqrt{n},2^n,n\log n,n!,n,1$$

Exercise 2.2. Prove or disprove: if $f(n)=O(g(n))$ and $g(n)=O(h(n))$, then $f(n)=O(h(n))$. (In other words, is Big-O transitive?)

Exercise 2.3. For each of the following recurrences, use the Master Theorem to determine the asymptotic bound, or explain why the Master Theorem does not apply.

(a) $T(n)=4T(n/2)+n$

(b) $T(n)=2T(n/2)+n\log n$

(c) $T(n)=3T(n/3)+n$

(d) $T(n)=T(n/2)+n$

Exercise 2.4. Consider a dynamic array that triples (instead of doubles) its capacity when full. Prove that the amortized cost of an append operation is still $O(1)$. How does the constant factor compare to the doubling strategy?

Exercise 2.5. An algorithm processes an array of $n$ elements as follows: for each element, it performs a binary search over the preceding elements. What is the overall time complexity? Express your answer in Big-Theta notation.

Recursion and Divide-and-Conquer

Recursion is one of the most powerful techniques in algorithm design: solving a problem by breaking it into smaller instances of the same problem. In this chapter we study recursion from the ground up, connect it to mathematical induction, and then develop the divide-and-conquer strategy — splitting a problem into independent subproblems, solving each recursively, and combining the results. We illustrate these ideas with four algorithms: binary search, fast exponentiation, the Euclidean algorithm for greatest common divisors, and the closest pair of points.

Recursion

Some problems have a natural recursive structure: the solution depends on solving one or more smaller instances of the same problem. When we translate this structure into code, we get a recursive function — a function that calls itself. This is not mere circularity: each call works on a smaller instance of the problem, and eventually the instances become small enough to solve directly. Every recursive function has two essential ingredients:

1. Base case. One or more input sizes for which the answer is immediate, without further recursion.
2. Recursive case. For larger inputs, the function reduces the problem to one or more smaller instances and combines the results.

Consider a simple example: computing the factorial $n!=1\cdot 2\cdot \dots \cdot n$.

function factorial(n: number): number {
  if (n <= 1) return 1;   // base case
  return n * factorial(n - 1); // recursive case
}

The base case is $n\le 1$, where we return 1. The recursive case multiplies $n$ by the factorial of $n-1$. Each recursive call reduces the argument by 1, so the chain of calls eventually reaches the base case:

$$\text{factorial}(4)=4\cdot \text{factorial}(3)=4\cdot 3\cdot \text{factorial}(2)=4\cdot 3\cdot 2\cdot \text{factorial}(1)=4\cdot 3\cdot 2\cdot 1=24.$$

The call stack

To understand how recursion works at runtime, we need to understand how computers handle function calls in general. Whenever any function is called — recursive or not — the runtime needs to remember where to return after the call finishes, and what values the local variables had. It stores this information in a frame: a block of memory holding the function's arguments, local variables, and the return address (the point in the calling code to resume after the call completes).

These frames are organized in a call stack — a stack data structure where each new call pushes a frame on top, and each return pops one off. For ordinary (non-recursive) code, the stack is typically shallow — for example, if main calls f, which calls g, the stack is only three frames deep. But with recursion, the same function can appear many times on the stack simultaneously, each frame representing a different invocation with different argument values.

For factorial(4), the stack grows to depth 4 before the base case is reached:

factorial(4)  — waiting for factorial(3)
  factorial(3)  — waiting for factorial(2)
    factorial(2)  — waiting for factorial(1)
      factorial(1)  — returns 1
    factorial(2)  — returns 2 × 1 = 2
  factorial(3)  — returns 3 × 2 = 6
factorial(4)  — returns 4 × 6 = 24

Each frame occupies memory, so a recursion of depth $d$ uses $O(d)$ stack space. For factorial(n), the depth is $n$, so the space complexity is $O(n)$.

Stack overflow

The call stack has a fixed maximum size, set by the operating system or the language runtime. When a recursion goes too deep, the stack runs out of space, and the program crashes with a stack overflow error. This is not an abstract concern — it happens easily in practice. For example, our factorial function works fine for small inputs, but calling factorial(100000) will likely crash:

factorial(100000); // RangeError: Maximum call stack size exceeded

In JavaScript and TypeScript, the default stack size typically allows around 10,000–15,000 frames (the exact limit depends on the runtime and the size of each frame). Other languages have similar limits.

This is an important practical consideration when choosing between a recursive and an iterative solution. Any recursion can be rewritten as a loop with an explicit stack, trading the elegance of recursion for safety against overflow. But for some problems the clarity and elegance of the recursive solution outweigh the cost. For algorithms where the recursion depth is logarithmic (like binary search, with depth $O(\log n)$), stack overflow is never a concern — even for $n=10^{18}$, the depth is only about 60. But for algorithms where the depth is linear in the input (like our factorial), an iterative version may be preferable for large inputs.

Common pitfalls

Two mistakes arise frequently when writing recursive functions:

1. Missing base case. Without a base case, the recursion never terminates:

   function infiniteRecursion(n: number): number {
     return n * infiniteRecursion(n - 1); // no base case!
   }
   

   This is not an algorithm in the sense of Definition 1.1 — it does not terminate.

2. Subproblems that do not shrink. Even with a base case, the recursion must make progress:

   function noProgress(n: number): number {
     if (n <= 1) return 1;
     return n * noProgress(n); // n does not decrease!
   }
   

   This function never reaches the base case for $n>1$.

Recursion and mathematical induction

Mathematical induction is a proof technique for showing that a statement is true for every element of a well-ordered sequence — most commonly the natural numbers, but the idea applies whenever instances can be ranked by size (array lengths, tree depths, and so on). It works in two steps. First, you show the statement is true for the smallest case (usually $n=0$ or $n=1$) — this is the base case. Second, you show that if the statement is true for some number $k$, then it must also be true for $k+1$ — this is the inductive step. Together, these two steps create a chain of reasoning: the base case establishes the first domino, and the inductive step guarantees that each domino knocks over the next, so the statement holds for all natural numbers.

There is a deep connection between this technique and recursion. Induction proves that a property holds for all natural numbers; recursion computes a value for all valid inputs. The structures are parallel:

This parallel is not a coincidence — it is the foundation for proving recursive algorithms correctness. To prove that a recursive function computes the right answer, we use strong induction (also called complete induction): assume the function works correctly for all inputs smaller than $n$, and show it works correctly for input $n$.

Definition 3.1 - Correctness of a recursive algorithm

A recursive algorithm is correct if:

1. It produces the correct answer on all base cases.
2. If the algorithm produces the correct answer on every strictly smaller subproblem, then it also produces the correct answer on the current problem.

When we implement a recursive algorithm as a function in code, these two conditions translate directly: the base case corresponds to the if branch that returns a value without recursing, and the recursive case corresponds to the branch that calls the function on a smaller input and combines the result. Condition 2 becomes: if every recursive call on a strictly smaller input returns the correct answer, then the current call also returns the correct answer.

Not every function is an algorithm — a function might not terminate, or might not solve a well-defined problem — but when a recursive function does implement an algorithm, proving it correct means verifying exactly these two conditions.

Example 3.1: Correctness of factorial.

Base case. When $n\le 1$, the function returns 1, and indeed $0!=1!=1$.

Inductive step. Assume factorial(k) returns $k!$ for all $k<n$. Then factorial(n) returns $n\cdot \text{factorial}(n-1)=n\cdot (n-1)!=n!$. $\square$

Divide and conquer

Divide and conquer is a specific recursion pattern that solves a problem by:

1. Divide: split the input into two or more smaller subproblems of the same type.
2. Conquer: solve each subproblem recursively (or directly if it is small enough).
3. Combine: merge the subproblem solutions into a solution for the original problem.

Not every recursive algorithm is divide-and-conquer. The factorial function above reduces the problem by a constant amount (from $n$ to $n-1$), which is sometimes called decrease and conquer. True divide-and-conquer algorithms typically split the input by a constant fraction (usually in half), leading to logarithmic recursion depth and often dramatically better performance.

The running time of a divide-and-conquer algorithm is typically expressed as a recurrence of the form

$$T(n)=aT(n/b)+f(n),$$

where $a$ is the number of subproblems, $n/b$ is their size, and $f(n)$ is the cost of dividing and combining.

Note that $a$ and $b$ need not be equal: $b$ describes how the input is partitioned (a structural choice), while $a$ describes how many of those parts the algorithm actually recurses on (an algorithmic choice). For example, binary search splits the array in two ($b=2$) but recurses on only one half ($a=1$); merge sort also splits in two ($b=2$) but must recurse on both halves ($a=2$). An algorithm can even have $a>b$: Karatsuba multiplication splits each number into two halves ($b=2$) but produces three recursive subproblems ($a=3$) from clever algebraic rearrangement. The relationship between $a$ and $b$ is what ultimately determines the algorithm's growth rate. As we saw in Chapter 2, the Master Theorem often gives us the asymptotic estimate for $T(n)$ directly.

Binary search

Our first divide-and-conquer algorithm is one of the most important ones: binary search. It finds the position of a target value in a sorted array by repeatedly halving the search space.

The problem

Input: A sorted array $A[\mathrm{0..}n-1]$ of numbers and a target value $x$.

Output: An index $i$ such that $A[i]=x$, or $-1$ if $x$ is not in $A$.

The algorithm

The idea is simple: compare $x$ with the middle element of the array.

• If they match, return the index.
• If $x$ is smaller, recurse on the left half.
• If $x$ is larger, recurse on the right half.

Each step eliminates half of the remaining elements.

Recursive implementation

Since binary search is a divide-and-conquer algorithm, it is most natural to express it recursively. The function takes an array, a target, and the current search range (low and high). The two base cases are: (1) the range is empty — the element is not present; (2) the middle element matches — we return its index. The recursive cases narrow the range to one half:

export function binarySearchRecursive(
  arr: number[],
  element: number,
  low: number = 0,
  high: number = arr.length - 1,
): number {
  if (low > high) return -1; // base case: empty range

  const mid = Math.floor((low + high) / 2);
  const midVal = arr[mid]!;

  if (midVal === element) {
    return mid; // base case: found
  } else if (midVal < element) {
    return binarySearchRecursive(arr, element, mid + 1, high); // search right half
  } else {
    return binarySearchRecursive(arr, element, low, mid - 1); // search left half
  }
}

This implementation directly mirrors the divide-and-conquer description: each call either solves the problem immediately (base case) or delegates to a single subproblem of half the size.

Tracing through an example

Let $A=[1,3,5,7,9,11,13]$ and $x=9$.

After only 3 comparisons (and 3 recursive calls), we have found the element in a 7-element array. A linear scan might have taken up to 7 comparisons.

Correctness

We prove correctness by induction on the size of the search range $h=\text{high}-\text{low}+1$.

Base case. When $\text{low}>\text{high}$ (empty range, $h\le 0$), the element cannot be present, and the function correctly returns $-1$.

Inductive step. Assume the function returns the correct result for all ranges smaller than $h$. For a range of size $h$, the function computes $\text{mid}$ and compares $A[\text{mid}]$ with $x$:

• If $A[\text{mid}]=x$, we return $\text{mid}$. Correct.
• If $A[\text{mid}]<x$, then since $A$ is sorted, $x$ cannot be in $A[\text{low}..\text{mid}]$. The recursive call searches $A[\text{mid}+\mathrm{1..}\text{high}]$, a strictly smaller range, so by the inductive hypothesis it returns the correct answer.
• The case $A[\text{mid}]>x$ is symmetric. $\square$

From recursion to iteration

Notice that the recursive binary search is tail-recursive: the recursive call is the very last operation in each branch — the function returns whatever the recursive call returns, without doing any further computation. Tail-recursive functions can always be transformed into a simple loop: we replace the recursive calls with assignments to the parameters and repeat.

Of course, even without this manual transformation, the computer already executes the recursion iteratively at the hardware level — using the call stack we discussed earlier in this chapter. Each recursive call pushes a new frame, and each return pops one off. But that mechanical translation is wasteful: it allocates a stack frame for every call, even though the caller does nothing with the result except pass it through. Transforming a tail-recursive function into a loop eliminates the stack entirely — the parameters are simply updated in place and control jumps back to the top of the function. The reason we can eliminate the stack is precisely that the function is tail-recursive: since nothing remains to be done after the recursive call returns, the caller's frame holds no state that is still needed, so there is nothing to save and no need for a stack frame at all. This is a general property — any tail-recursive function can be mechanically rewritten as a loop without a stack.

Let us apply this transformation to our recursive binary search:

export function binarySearch(arr: number[], element: number): number {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    const midVal = arr[mid]!;

    if (midVal === element) {
      return mid;
    } else if (midVal < element) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1;
}

The variables low and high play exactly the same role as the parameters of the recursive version — they define the current subproblem. Each iteration halves the range, just as each recursive call did. The iterative version has the advantage of using $O(1)$ space instead of $O(\log n)$, because it avoids the overhead of the call stack. In practice, both versions are fine for binary search (the recursion depth is at most about 60 even for $n=10^{18}$), but the iterative form is conventional and marginally faster.

Complexity analysis

Each step halves the search range. Starting from $n$ elements, after $k$ steps we have at most $n/2^k$ elements. When $n/2^k=1$ there is still one element left to compare, so the search has not yet terminated. The range becomes empty — and the process terminates — when $n/2^k<1$, i.e., after at most $k=\lfloor {\log }_{2}n\rfloor +1$ steps.

• Time complexity: $O(\log n)$ (both versions).
• Space complexity: $O(\log n)$ for the recursive version (call stack depth); $O(1)$ for the iterative version.

Using the Master Theorem on the recurrence: $T(n)=T(n/2)+O(1)$. Here $a=1$, $b=2$, $n^{{\log }_{b}a}=n^0=1$. Since $f(n)=O(1)=\Theta (n^{{\log }_{b}a})$, Case 2 gives $T(n)=\Theta (\log n)$.

Comparison with linear search

For comparison, here is the linear search algorithm:

export function linearSearch<T>(arr: T[], element: T): number {
  let position = -1;
  let currentIndex = 0;

  while (position < 0 && currentIndex < arr.length) {
    if (arr[currentIndex] === element) {
      position = currentIndex;
    } else {
      currentIndex++;
    }
  }
  return position;
}

Linear search works on any array (not just sorted ones) but takes $O(n)$ time. Binary search requires a sorted array but is exponentially faster:

This dramatic improvement — from linear to logarithmic — is the hallmark of the divide-and-conquer approach. The key insight is that each comparison does not eliminate just a single element but half of the remaining elements.

Fast exponentiation (exponentiation by squaring)

Our second example addresses the problem of computing $b^n$ efficiently.

The problem

Input: A number $b$ (the base) and a non-negative integer $n$ (the exponent).

Output: The value $b^n$.

Naive approach

The straightforward approach multiplies $b$ by itself $n$ times:

export function powSlow(base: number, power: number): number {
  let result = 1;
  for (let i = 0; i < power; i++) {
    result = result * base;
  }
  return result;
}

This performs $n$ multiplications, so it runs in $O(n)$ time.

Exponentiation by squaring

We can do much better by observing a simple mathematical identity:

$$b^n=\{\begin{array}{ll}1& \text{if }n=0,\\ (b^{n/2}{)}^2& \text{if }n\text{ is even},\\ b\cdot b^{n-1}& \text{if }n\text{ is odd}.\end{array}$$

When $n$ is even, we compute $b^{n/2}$ once and square the result — a single multiplication instead of $n/2$ multiplications. When $n$ is odd, we reduce to an even exponent by extracting one factor of $b$.

The recurrence above translates directly into a recursive function — just as with binary search. Writing that recursive version is straightforward (see Exercise 3.3). Here, we skip the intermediate steps we took for binary search and jump straight to the optimized iterative version. As before, the recursive version is tail-recursive, so the same transformation applies: we replace recursive calls with assignments to the parameters and loop:

export function pow(base: number, power: number): number {
  let result = 1;

  while (power > 0) {
    if (power % 2 === 0) {
      base = base * base;
      power = power / 2;
    } else {
      result = result * base;
      power = power - 1;
    }
  }
  return result;
}

Tracing through an example

Let us compute $2^{10}$:

Result: $2^{10}=1024$. The naive approach would have used 10 multiplications; fast exponentiation used 5.

Correctness

Invariant: At the start of each iteration, $\text{result}\times {\text{base}}^{\text{power}}$ equals the original $b^n$.

• Initialization. $\text{result}=1$, $\text{base}=b$, $\text{power}=n$. The invariant $1\times b^n=b^n$ holds.
• Maintenance.
  • If power is even: we replace base with ${\text{base}}^2$ and power with $\text{power}/2$. Then $\text{result}\times ({\text{base}}^2{)}^{\text{power}/2}=\text{result}\times {\text{base}}^{\text{power}}$. Invariant preserved.
  • If power is odd: we replace result with $\text{result}\times \text{base}$ and power with $\text{power}-1$. Then $(\text{result}\times \text{base})\times {\text{base}}^{\text{power}-1}=\text{result}\times {\text{base}}^{\text{power}}$. Invariant preserved.
• Termination. When power $=0$, the invariant gives $\text{result}\times {\text{base}}^0=\text{result}=b^n$. $\square$

Complexity analysis

At each "odd" step, the exponent decreases by 1 (making it even). At each "even" step, the exponent halves. After at most two consecutive steps (one odd, one even), the exponent has been at least halved. Therefore the total number of steps is $O(\log n)$.

• Time complexity: $O(\log n)$.
• Space complexity: $O(1)$.

Alternatively, we can obtain a more precise asymptotic estimate directly from the Master Theorem. The recurrence for the recursive view is $T(n)=T(n/2)+O(1)$, the same as binary search, giving $\Theta (\log n)$.

The Euclidean algorithm for GCD

The greatest common divisor (GCD) of two positive integers $x$ and $y$ is the largest integer that divides both. It is one of the oldest algorithms known, recorded by Euclid around 300 BC.

The problem

Input: Two positive integers $x$ and $y$.

Output: $\gcd (x,y)$, the largest positive integer dividing both $x$ and $y$.

Naive approach

The brute-force approach tries every candidate from the smaller number downward. The GCD of $x$ and $y$ cannot exceed $\min (x,y)$, because no number larger than $x$ can divide $x$ (and likewise for $y$). So there is no point starting the search above the smaller of the two inputs:

export function gcdSlow(x: number, y: number): number {
  const min = Math.min(x, y);

  for (let i = min; i >= 2; i--) {
    if (x % i === 0 && y % i === 0) {
      return i;
    }
  }
  return 1;
}

This checks up to $\min (x,y)$ candidates, so its time complexity is $O(\min (x,y))$.

The Euclidean algorithm

The Euclidean algorithm is based on a key observation:

$$\gcd (x,y)=\gcd (y,x\mathrm{mod}y)$$

The modulo operation. The expression $x\mathrm{mod}y$ (pronounced "x mod y") denotes the remainder when $x$ is divided by $y$: for instance, $10\mathrm{mod}3=1$ because $10=3\times 3+1$, and $15\mathrm{mod}5=0$ because $5$ divides $15$ evenly. In TypeScript this is written x % y — we already used it in the naive GCD function above (x % i === 0). Formally, $x\mathrm{mod}y=x-\lfloor x/y\rfloor \cdot y$, and the result always satisfies $0\le (x\mathrm{mod}y)<y$.