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

Average case analysis of marking algorithms

  • Author(s): Hirschberg, D. S.
  • Larmore, L. L.
  • et al.
Abstract

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
Current View