How Robust are Average Complexity Measures? A Statistical Case Study
by Suman Kumar Sourabh and Soubhik Chakraborty.
Average case analysis forms an interesting and intriguing part of algorithm theory since it explains why some algorithms with bad worst-case complexity can be better on the average. Famous examples are the quicksort, simplex method and the wide variety of computer graphics and computational geometry algorithms. Here we make a statistical case study on the robustness of average complexity measures, which are derived assuming uniform distribution, for non-uniform inputs (both discrete and continuous).
algorithm, robustness, average case complexity, worst-case complexity, replacement sort
Suman Kumar Sourabh, firstname.lastname@example.org
Soubhik Chakraborty, email@example.com
R. G. Graf, firstname.lastname@example.org
READING THE ARTICLE: You can read the article in
portable document (.pdf) format (246548 bytes.)
NOTE: The content of this article is the intellectual property of the authors, who retains all rights to future publication.
This page has been accessed 2268 times since July 24,2006.
Return to the Home Page.