## 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

**Authors:**

Suman Kumar Sourabh, sourabh.suman@rediffmail.com

Soubhik Chakraborty, soubhikc@yahoo.co.in

**Editor:**
R. G. Graf, rgraf@sunstroke.sdsu.edu

**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.