Chapter 2 · Analysis Framework
Orders of growth
Seven functions that describe almost every algorithm you will meet. Drag n, switch to a logarithmic axis, and feel the difference between "slow" and "never finishes".
y-axis
⏱️ How long at 10⁹ operations per second?
Each cell is f(n) basic operations divided by the computer's speed. Green: under a second. Yellow: under a day. Red: longer than a day. The age of the universe is about 4.4 × 10¹⁷ seconds (≈ 1.4 × 10¹⁰ years).
✖️2 What happens when n doubles?
Pick n. Each row shows f(2n) / f(n): how many times more work the same algorithm does on an input twice as big.
🧮 Limit rule: compare f and g
Levitin §2.2: look at lim f(n)/g(n) as n → ∞. 0 means f grows slower (f ∈ O(g)); a positive constant means same order (f ∈ Θ(g)); ∞ means f grows faster (f ∈ Ω(g)).
Custom functions use n, + − * / ^, ( ), and log2, ln, log10, sqrt, exp, fact.
How to read this
- Each colored curve is one function of the input size n; the label at the end of a curve names it. Hover (or touch) the chart to read every value at one n.
- Linear axis: the chart is scaled to the biggest polynomial you have switched on. Exponential curves shoot off the top: that vertical escape is the lesson.
- Logarithmic axis: each grid line is 10 times the one below, so every curve fits. Polynomials become gentle curves; 2ⁿ becomes a straight line; n! bends upward even on this axis. The dashed line is how many operations fit in one second at the chosen speed.
- Press play to sweep n from 1 upward. The pseudocode panel highlights the loop shape that produces the curve that is currently biggest; click a legend entry to jump to its loop shape.
Try this
- On the linear axis with n up to 30, find where 2ⁿ overtakes n³ (between 9 and 10) and where n! overtakes 2ⁿ (at n = 4). Use the Predict button first.
- In the time table, find the largest n that a 2ⁿ algorithm can handle in under a second at 10⁹ operations/second (n ≈ 30). Switch to 10¹⁵ operations/second: it only moves to about 50. Faster hardware barely helps exponential algorithms.
- Double n from 100 to 200: an n² algorithm does 4 times the work, n³ does 8 times, and 2ⁿ does 2¹⁰⁰ times.
- In the limit panel, compare n(n−1)/2 with n². Predict first. (The limit is 1/2, so they are the same order: Θ(n²).)
- Compare log₂ n with √n. Even though log₂ n is bigger for small n (try the plot), the ratio goes to 0: every positive power of n eventually beats every power of log n.