K Sort Revisited for Negative Binomial Inputs
Kiran Kumar Sundararajan, Mita Pal, Soubhik Chakraborty, Bijeeta Pal · 2012
Parameterized complexity is a branch of computational complexity theory in computer science that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input. In this context, the present paper examines, through computer experiments, the behavior of a new version of Quick sort, called K-sort, when the sorting elements follow a Negative Binomial distribution. A computer experiment is a series of runs of a code for various inputs. A deterministic computer experiment is one which produces identical results if the code is re-run for identical inputs. If the response of the computer experiment is the complexity of the underlying algorithm then it is deterministic for a fixed input but may be taken as stochastic for fixed input size and randomly varying input elements as in sorting. Even otherwise we can advocate stochastic modeling imagining the response as stochastic to achieve cheap and efficient prediction.