Average Case Analysis of Marking Algorithms

descriptionPublicationkeyboard_double_arrow_right Article 01 Nov 1986 United States English Publisher:Society for Industrial & Applied Mathematics (SIAM)Journal:SIAM Journal on Computing, volume 15, pages 1,069-1,074 (issn: 0097-5397, eissn: 1095-7111,

Copyright policy )

Authors: Hirschberg, D. S.; Larmore, L. L.;

doi: 10.1137/0215076

Average Case Analysis of Marking Algorithms

- Summary
- Subjects
- Metrics

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 is O(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).

Country

United States

Related Organizations

University of California, Irvine
United States
University of California
United States
California State University, Dominguez Hills
United States

Keywords

Data structures, garbage collection, Analysis of algorithms and problem complexity, average case time complexity, average size, Lindstrom marking algorithm, Wegbreit bit stack

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	3
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average