On Why the Parameters of Input Distributions Need be Taken Into Account
for a More Precise Evaluation of Complexity for Certain Algorithms
by Soubhik Chakraborty, Mausumi Bose and Kumar Sushant.
Taking a dip into what is called the "gold standard" in research,
the authors show how parameters of the input distributions play a
crucial role in complexity analysis for certain algorithms such as sorting,
citing the Binomial input case for replacement sort an illustration,
indicating how ties play a crucial role for discrete distributions.
The relationship between computer experiments and algorithmic complexity is
also discussed(see also our paper in InterStat December2004#2 issue)
Replacement sort, parameters of input distribution,
average complexity, interchanges, stochastic realisation of a
deterministic computer experiment
Soubhik Chakraborty, email@example.com
Mausumi Bose, firstname.lastname@example.org
Kumar Sushant, email@example.com
Joseph McKean, firstname.lastname@example.org
READING THE ARTICLE: You can read the article in
portable document (.pdf) format (139476 bytes.)
NOTE: The content of this article is the intellectual property of the authors, who retains all rights to future publication.
This page has been accessed 2261 times since July 24, 2006.
Return to the Home Page.