Complexity verification through design and analysis of computer experiments. (21st November 2019)

• Record Type: Journal Article
• Authors: Singh, Niraj Kumar; Chakraborty, Soubhik; Mallick, Dheeresh Kumar
• Is Part Of: International journal of computational complexity and intelligent algorithms. Volume 1:Number 2(2019)
• Page Start: 178
• Page End: 195
• Publication Date: 2019-11-21
• Subjects: average case complexity -- statistical bound -- empirical-O -- quick sort -- smart sort -- parameterised complexity -- factorial design -- statistical significance; Computational complexity -- Periodicals; Heuristic algorithms -- Periodicals; Neural networks (Computer science) -- Periodicals; 006.3
• Languages: English
• ISSNs: 2048-4720

Abstract

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 ( n log2 n ) complexity for smart sort is conjectured as result of study for various regression models and factorial design experiments.