Skiena, Chapter 2

Algorithm Analysis

The RAM model, Big Oh, growth rates, dominance relations, and logarithms. The tools that let you compare algorithms without running them.

Prerequisites: Chapter 1 + Basic algebra. That's it.

Chapters

Simulations

Quizzes

Chapter 0: Why Analyze Algorithms?

You have two algorithms that solve the same problem. Both are correct. How do you choose between them? You could time them on your computer, but that tells you about your computer and your test data, not about the algorithms themselves.

What we really want is a way to predict how an algorithm will perform on inputs of any size, on any machine. We want to separate the essential efficiency of the algorithm from the accidents of implementation. That is what algorithm analysis gives us.

The key insight: rather than timing programs, we count the number of fundamental operations as a function of input size n. An algorithm that does 2n² operations will always eventually lose to one that does 100n operations, no matter how fast the first machine is.

The big picture: Algorithm analysis lets you predict the future. Before you write a single line of code, you can determine whether your approach will scale to the inputs you care about. A quadratic algorithm on a million items will take a trillion operations. A linear one will take a million. No amount of hardware fixes that gap.

Why is counting operations better than timing programs?

Timing is always faster Counting operations gives machine-independent predictions about how the algorithm scales Counting operations gives exact running times

Chapter 1: The RAM Model

To count operations, we need to agree on what counts as "one operation." The Random Access Machine (RAM) model is our contract. It assumes:

• Each simple operation (+, -, *, /, comparison, assignment) takes one time step.
• Loops and function calls are not simple operations -- they cost the sum of their inner operations.
• Memory access takes one step regardless of address (no caching effects).

The RAM model is a simplification. Real computers have caches, pipelines, and branch predictors. But the simplification works remarkably well because it captures the essential growth rate of running time.

Best, worst, and average case: For any input size n, different inputs can cause different running times. The worst case is the slowest input of size n. The best case is the fastest. The average case averages over all inputs. Worst case is most useful in practice because it provides a guarantee.

Why worst case? Think of it like a casino trip. The best case (you own the place) is too unlikely to plan for. The average case (you lose 87% of your money) is hard to compute and debatable. The worst case (you lose everything) is easy to calculate and likely enough to matter.

In the RAM model, what is the cost of accessing the ith element of an array?

One step (constant time), regardless of i i steps log(i) steps

Chapter 2: Big Oh Notation

Real complexity functions have bumps and wiggles. An algorithm might run slightly faster when n is a power of 2. We don't care about these details. Big Oh notation lets us ignore constant factors and lower-order terms, focusing on the growth rate.

f(n) = O(g(n)) means: ∃ constants c, n₀ such that f(n) ≤ c · g(n) for all n ≥ n₀

In plain English: f grows no faster than g, up to a constant factor. The O is an upper bound.

f(n) = Ω(g(n)) means: ∃ constants c, n₀ such that f(n) ≥ c · g(n) for all n ≥ n₀

Ω is a lower bound. And when both hold:

f(n) = Θ(g(n)) means: f(n) = O(g(n)) AND f(n) = Ω(g(n))

Θ is a tight bound. It says f and g grow at the same rate.

Quick examples:
3n² − 100n + 6 = O(n²) because 3n² ≥ 3n² − 100n + 6 when n ≥ 0.
3n² − 100n + 6 = Ω(n²) because 2n² ≤ 3n² − 100n + 6 when n > 100.
3n² − 100n + 6 = Θ(n²) because both O and Ω apply.
3n² − 100n + 6 ≠ O(n) because no constant c makes cn ≥ 3n² for large n.

Big Oh Visualizer

See f(n) = 3n² − 100n + 6 squeezed between c₁·n² and c₂·n². Adjust c to find valid bounds.

c (upper) 3.0

What does f(n) = O(n²) mean?

f(n) grows no faster than n², up to a constant factor, for sufficiently large n f(n) is exactly n² f(n) is always less than n²

Chapter 3: Growth Rates

The power of Big Oh is that it groups algorithms into classes. Within a class, constant factors don't matter. Between classes, the slower-growing function always wins for large enough n.

Here are the classes that matter, from fastest to slowest growing:

O(1)

Constant. Array access, hash lookup.

↓

O(log n)

Logarithmic. Binary search. Barely grows.

↓

O(n)

Linear. Single pass through data.

↓

O(n log n)

Superlinear. Mergesort, quicksort.

↓

O(n²)

Quadratic. All pairs. Insertion sort.

↓

O(2ⁿ)

Exponential. All subsets. Impractical for n > 40.

↓

O(n!)

Factorial. All permutations. Impractical for n > 20.

The wall: At 1 nanosecond per operation, an O(n²) algorithm on n = 1,000,000 takes 11.5 days. An O(n log n) algorithm takes 0.02 seconds. An O(2ⁿ) algorithm on n = 50 takes 13 days. On n = 100, it takes 40 trillion years. There is no hardware fast enough to cross the polynomial/exponential divide.

Growth Rate Table

Time at 1 ns/operation for different n values. Red = impractical (over 1 year).

Which growth rate remains practical for n = 1 billion?

O(n log n) O(n²) O(2ⁿ)

Chapter 4: Dominance Relations

We say a faster-growing function dominates a slower-growing one. The dominance hierarchy is:

n! >> 2ⁿ >> n³ >> n² >> n log n >> n >> log n >> 1

Is 2ⁿ⁺¹ = Θ(2ⁿ)? Yes! Because 2ⁿ⁺¹ = 2 · 2ⁿ, and constant factors don't matter in Big Oh. But is 2²ⁿ = Θ(2ⁿ)? No! Because 2²ⁿ = (2ⁿ)², and squaring is NOT a constant factor.

Go back to the definition. Whenever Big Oh confuses you, substitute into the formal definition and check whether the inequality holds. "Is f = O(g)?" becomes "Can I find c such that f(n) ≤ c · g(n) for large n?" This mechanical approach never fails.

Dominance Visualizer

Pick two growth classes to compare. Watch how quickly the dominant function pulls away.

Is 2²ⁿ = O(2ⁿ)?

Yes, they are both exponential No, because 2²ⁿ = (2ⁿ)², which grows as the square of 2ⁿ It depends on n

Chapter 5: Adding & Multiplying

Two rules govern how Big Oh combines:

O(f(n)) + O(g(n)) = O(max(f(n), g(n)))

When you add functions, the dominant one wins. This is why n³ + n² + n + 1 = O(n³). The smaller terms are small potatoes.

O(f(n)) · O(g(n)) = O(f(n) · g(n))

When you multiply, both matter. An O(n) loop inside an O(n) loop gives O(n²). An O(n) loop inside an O(log n) binary search gives O(n log n).

Constant factors vanish: O(c · f(n)) = O(f(n)) for any constant c. This is why an algorithm that does 7n steps is still O(n). The constant 7 gets absorbed into the Big Oh. This is the whole point: we care about growth rate, not constants.

Transitivity: If f(n) = O(g(n)) and g(n) = O(h(n)), then f(n) = O(h(n)). This lets us chain comparisons: since n = O(n log n) and n log n = O(n²), we know n = O(n²).

What is O(n²) + O(n)?

O(n²), because the dominant term wins O(n³) O(n² + n)

Chapter 6: Logarithms

A logarithm is an inverse exponential. If 2^x = n, then x = log₂(n). Logarithms arise whenever we repeatedly halve things (binary search), double things (tree height), or multiply things (number of digits).

Three places logarithms appear:
1. Binary search. Each comparison halves the search space. After log₂ n comparisons, only one item remains.
2. Tree height. A balanced binary tree on n nodes has height log₂ n, because each level doubles the number of nodes.
3. Number of digits. The number n has 1 + ⌊log₁₀ n⌋ decimal digits. Writing down a big number takes logarithmic space.

Bases don't matter in Big Oh. Since log_a n = log_b n / log_b a, changing the base only multiplies by a constant. So O(log₂ n) = O(log₁₀ n) = O(ln n). We just write O(log n).

Logarithms grow incredibly slowly. log₂(1,000,000) ≈ 20. log₂(1,000,000,000) ≈ 30. This is why binary search is so fast. Even on a billion items, it needs only about 30 comparisons.

How Slow Does log n Grow?

Drag n across six orders of magnitude. Watch log n barely change.

log₁₀(n) 10000

Why don't we specify the base of the logarithm in Big Oh?

All bases give the same answer Changing the base only multiplies by a constant, and Big Oh absorbs constants We always use base 2

Chapter 7: The Algorithm Race

Time to see growth rates compete head-to-head. This simulation races algorithms with different complexities on the same input size. Watch how the polynomial algorithms pull ahead of exponential ones.

Growth Rate Race

Drag the slider to increase input size n. The bar chart shows the number of operations for each complexity class (log scale). Red means "would take over 1 year at 1 ns/op."

n 10

Try this: Set n=10. All algorithms are fast. Now slowly increase to n=20, 30, 40. Watch 2ⁿ and n! hit the red zone (over a year) while n log n barely budges. This is why complexity class matters more than constant factors or hardware speed.

At n=40, which algorithms are still practical (under 1 second at 1 ns/op)?

O(1), O(log n), O(n), O(n log n), and O(n²) Everything except O(n!) All of them

Chapter 8: Connections

Algorithm analysis is the language we use throughout the rest of the book. Here is how the concepts connect:

Concept	Where It Leads
O(log n)	Chapter 3: BST operations, Chapter 4: binary search
O(n log n)	Chapter 4: mergesort, heapsort, quicksort
O(n + m)	Chapter 5: BFS and DFS on graphs
O(n²) and O(n³)	Chapter 8: dynamic programming tables
Exponential/factorial	Chapter 9: NP-completeness

Skiena's take-home lessons from Chapter 2:
• The Big Oh notation and worst-case analysis greatly simplify our ability to compare algorithm efficiency.
• A small variety of time complexities (log n, n, n log n, n², 2ⁿ, n!) account for most algorithms in practice.
• Logarithms grow so slowly they should be considered almost-constant. Any O(log n) algorithm is blazing fast.
• When confused by Big Oh, go back to the formal definition and check the inequality.

An algorithm takes 5n² + 3n + 12 operations. What is its Big Oh class?

O(5n²) O(n²) O(n² + n)