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

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

Return to the InterStat Home Page.