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

Average case analysis of marking algorithms

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
For improved accessibility of PDF content, download the file to your device.
Current View