\input zb-basic
\input zb-matheduc
\iteman{ZMATH 2006e.03274}
\itemau{Sourabh, Suman Kumar; Chakraborty, Soubhik}
\itemti{How robust are average complexity measures? A statistical case study.}
\itemso{InterStat, No. 7, 17 p. (2006).}
\itemab
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). (Author's abstract)
\itemrv{~}
\itemcc{K95 K75}
\itemut{algorithms; robustness; average case complexity; worst-case complexity; replacement sort}
\itemli{}
\end