Skip to main content
Open Access Publications from the University of California

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).

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View