Complexity verification through design and analysis of computer experiments

This research article is a systematic study towards exploring the parameterised behaviour of smart sort, a comparison based sorting algorithm. Our observation for quick sort led us to conjecture that for sufficiently large samples of fixed size, the average case runtime complexity is: yavg(n, td) = Oemp(td), where yavg denotes the average complexity with parameters n and td denoting the input size and frequency of an element (tie density) respectively. The notation Oemp (also called empirical-O) is the statistical bound estimate obtained by running computer experiments. Performance of heap sort is better for discrete inputs with low k values (or equivalently high td values) and the runtime reaches to maximum beyond a threshold k. These two observations are opposite in their behaviour. The smart sort, which is designed by combining the key functions of standard quick and heap sort algorithms, is expected to behave optimally with respect to the different input parameters. The robustness of average case Oemp(nlog2n) complexity for smart sort is conjectured as result of study for various regression models and factorial design experiments.