Telescoping in Algorithms: Prefix Sums, Quicksort and the Potential Method

The first two papers in this series showed that one identity, the sum of f(k) - f(k+1) from k=1 to n equals f(1) - f(n+1), evaluates the sum of 1/(k(k+1)) and underlies the Z-transform, Lyapunov stability and the CIC filter. This paper follows the same identity into the design and analysis of algorithms. Prefix sums answer any range-sum query with one subtraction; their two-dimensional version, the integral image, sums any rectangle of an image with four look-ups and powers real-time object detection; Fenwick trees keep prefix sums current under updates by telescoping along the binary digits of an index. On the analysis side, the exact average cost of Quicksort, 2(n+1)H(n) - 4n comparisons, falls out of a recurrence that is telescoped twice, and the final step is the partial fraction split of Paper 1 with a different numerator; its asymptotic constant involves Euler's constant, the open problem of Paper 1. Finally, we explain why growable arrays must copy their contents and why they grow geometrically, introduce amortised analysis and its three classical methods, and show that the potential method is telescoping by definition, with exact bounds for a binary counter and a growing array.