id: 02369983
dt: j
an: 2006e.03274
au: Sourabh, Suman Kumar; Chakraborty, Soubhik
ti: How robust are average complexity measures? A statistical case study.
so: InterStat, No. 7, 17 p. (2006).
py: 2006
pu: ,
la: EN
cc: K95 K75
ut: algorithms; robustness; average case complexity; worst-case complexity;
replacement sort
ci:
li:
ab: 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)
rv: