Article: Complexity verification through design and analysis of computer experiments Journal: International Journal of Computational Complexity and Intelligent Algorithms (IJCCIA) 2019 Vol.1 No.2 pp.178 - 195 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(nlog2n) complexity for smart sort is conjectured as result of study for various regression models and factorial design experiments. Inderscience Publishers - linking academia, business and industry through research

Title: Complexity verification through design and analysis of computer experiments

Authors: Niraj Kumar Singh; Soubhik Chakraborty; Dheeresh Kumar Mallick

Addresses: Department of Computer Science and Engineering, Birla Institute of Technology, Mesra, 835215, India ' Department of Mathematics, Birla Institute of Technology, Mesra, 835215, India ' Department of Computer Science and Engineering, Birla Institute of Technology, Mesra, 835215, India

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: y_avg(n, t_d) = O_emp(t_d), where y_avg denotes the average complexity with parameters n and t_d denoting the input size and frequency of an element (tie density) respectively. The notation O_emp (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 t_d 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 O_emp(nlog₂n) complexity for smart sort is conjectured as result of study for various regression models and factorial design experiments.

Keywords: average case complexity; statistical bound; empirical-O; quick sort; smart sort; parameterised complexity; factorial design; statistical significance.

DOI: 10.1504/IJCCIA.2019.103729

International Journal of Computational Complexity and Intelligent Algorithms, 2019 Vol.1 No.2, pp.178 - 195

Accepted: 24 Jun 2017
Published online: 26 Nov 2019 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article

Title: Complexity verification through design and analysis of computer experiments

Keep up-to-date