List of Figures
1.1 Quicksort compare counts: empirical and analytic, 23
1.2 Distributions for compares in quicksort, 30
1.3 Distributions for compares in quicksort (scaled and centered), 31
1.4 Empirical histogram for quick-sort compare counts, 32
2.1 Solutions to binary divide-and-conquer recurrences, 70
2.2 Periodic terms in binary divide-and-conquer recurrences, 71
2.3 lgN (top); ⌊lgN⌋ (middle); {lgN} (bottom), 74
2.4 Composition of the periodic function θ(1 – {lgN}), 75
2.5 Periodic and fractal terms in bit counting, 77
2.6 Divide-and-conquer for β = 3 and α = 2, 3, 4, 83
3.1 All binary trees with 1, 2, 3, 4, and 5 external nodes, 124
4.1 Ramanujan Q-distribution, 189
4.2 Ramanujan R-distribution, 193
Get An Introduction to the Analysis of Algorithms, Second Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.