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.
Abstract:
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)
Key Words:
Replacement sort, parameters of input distribution,
average complexity, interchanges, stochastic realisation of a
deterministic computer experiment
Authors:
Soubhik Chakraborty, soubhikc@yahoo.co.in
Mausumi Bose, mausumi@isical.ac.in
Kumar Sushant, kumarsushant@yahoo.com
Editor:
Joseph McKean, joe@stat.wmich.edu
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 292 times since July 24, 2006.
Return to the 
Home Page.