Average Case Analysis of Marking Algorithms
D. S. Hirschberg, Lawrence L. Larmore · SIAM Journal on Computing · 1986
The Lindstrom marking algorithm uses bounded workspace. Its time complexity is $0(n^2 )$ in all cases, but it has been assumed that the average case time complexity is $0(n\log n)$. It is proven that the average case time complexity is $\Theta (n^2 )$ for a wide variety of probability distributions. Similarly, the average size of the Wegbreit bit stack is shown to be $\Theta (n)$.