Donald Bren School of Information and Computer Sciences
Average case analysis of marking algorithms
- Author(s): Hirschberg, D. S.
- Larmore, L. L.
- et al.
The Lindstrom marking algorithm uses bounded workspace. Its time complexity is O(n^2) in all cases, but it has been assumed that the average case time complexity O(n lg n). It is proven that the average case time complexity is H(n^2). Similarly, the average size of the Wegbreit bit stack is shown to be H(n).