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

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 2559 times since July 24, 2006.

Return to the InterStat Home Page.