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

Average case analysis of marking algorithms


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