How Robust are Average Complexity Measures? A Statistical Case Study

by Suman Kumar Sourabh and Soubhik Chakraborty.

Abstract: 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).

Key Words: algorithm, robustness, average case complexity, worst-case complexity, replacement sort

Suman Kumar Sourabh,
Soubhik Chakraborty,

Editor: R. G. Graf,

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 2130 times since July 24,2006.

Return to the InterStat Home Page.