On How Statistics Provides a Reliable and Valid Measure for an Algorithm’s Complexity
by Soubhik Chakraborty, Kiran Kumar Sundararajan, Basant Kumar Das and Suman Kumar Sourabh.
Abstract:
Stochastic modelling of deterministic computer experiments was strongly
and correctly advocated by Prof. Jerome Sacks and others [see J. Sacks, W. Welch,
T. Mitchell and H. Wynn, Design and Analysis of Computer Experiments, Statistical
Science, vol. 4. No. 4, 1989] in order to reduce the cost of prediction, quantifying the
amount of accuracy sacrificed in the bargain. Following some of these guidelines, the
authors in the present manuscript have made an interesting statistical adventure by
empirically deriving the difficult O(nlogn) average case complexity of the popular
Quicksort algorithm. Since the strategy could be easily applicable, with little or no
modification, to any arbitrary algorithm of similar or nearly similar complexity and more
importantly where a formal theoretical proof might be found wanting, [see also the first
chapter in the book Data Structures and Algorithms by A. Aho, J. Hopcroft, J. Ullman,
Addison Wesley], the authors propose Statistics as a reliable and valid tool for measuring
an arbitrary algorithm’s time complexity. As an added attraction, the paper further shows
how the sorting efficiency of Quicksort is affected by input from specific distributions,
citing the Binomial case, indicating the motivation of further research in that direction in
the future, especially covering mixture distributions.
[note: a computer experiment is a series of runs of a code for various inputs; it is called
deterministic if feeding the same inputs leads to identical observations].
Key Words:
Quicksort(nonrecursive) algorithm, the big-O, time complexity, applied
regression analysis
Authors:
Soubhik Chakraborty, soubhikc@yahoo.co.in
Kiran Kumar Sundararajan,
Basant Kumar Das,
Suman Kumar Sourabh
Editor:
Joseph McKean,joe@stat.wmich.edu
READING THE ARTICLE: You can read the article in
portable document (.pdf) format (191473 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.