@article {MATHEDUC.02369983,
author = {Sourabh, Suman Kumar and Chakraborty, Soubhik},
title = {How robust are average complexity measures? A statistical case study.},
year = {2006},
journal = {InterStat},
number = {7},
issn = {1941-689X},
pages = {17 p.},
publisher = {,},
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). (Author's abstract)},
msc2010 = {K95xx (K75xx)},
identifier = {2006e.03274},
}