Help on query formulation
How robust are average complexity measures? A statistical case study. (English)
InterStat, No. 7, 17 p. (2006).
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)
Classification: K95 K75
Valid XHTML 1.0 Transitional Valid CSS!