Donald Bren School of Information and Computer Sciences
Efficient optimal pagination of scrolls
- Author(s): Larmore, L. L.
- Hirschberg, D. S.
- et al.
Diehr and Faaland developed an algorithm that finds the minimum sum of key length pagination of a scroll of n items, and which uses O(n lg n) time and O(n) space, solving a problem posed by McCreight. An improved algorithm is given which uses O(n) time and O(n) space.