
02369983
j
2006e.03274
Sourabh, Suman Kumar
Chakraborty, Soubhik
How robust are average complexity measures? A statistical case study.
InterStat, No. 7, 17 p. (2006).
2006
,
EN
K95
K75
algorithms
robustness
average case complexity
worstcase complexity
replacement sort
Average case analysis forms an interesting and intriguing part of algorithm theory since it explains why some algorithms with bad worstcase 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 nonuniform inputs (both discrete and continuous). (Author's abstract)