How many interchanges does the selection sort make for iid geometric(p) input?
Journal Title: Annals. Computer Science Series - Year 2009, Vol 7, Issue 2
Abstract
The note derives an expression for the number of interchanges made by selection sort when the sorting elements are iid variates from geometric distribution. Empirical results reveal we can work with a simpler model compared to what is suggestive in theory. The morale is that statistical analysis of an algorithm’s complexity has something to offer in its own right and should be therefore ventured not with a predetermined mindset to verify what we already know in theory. Herein also lies the concept of an empirical O, a novel although subjective bound estimate over a finite input range obtained by running computer experiments. For an arbitrary algorithm, where theoretical results could be tedious, this could be of greater use.
Authors and Affiliations
Debasish Sahani , Soubhik Chakraborty
Keywords
Related Articles
- EP ID EP96954
- DOI -
- Views 139
- Downloads 0
Structural equation modeling of choice of place of delivery in Nigeria
Medical problems are often experienced during child delivery in a poor place of delivery and health care. The use of immediate health indicator as direct proxies for choice making biases estimates that these proxies are...
Neuro-Fuzzy Expert System For Diagnosis Of Thyroid Diseases
The computerization of medical procedures has been identified to be one of the major challenges in the medical sector. Several techniques have been used in order to automate the processes in diagnosis of diseases; such p...
Are Subsequences of Decimal Digits of PI Random?
A lot has been done on the randomness of the decimal expansion of Pi with extensive tests of randomness that are used to distinguish good from not-so-good random number generators when applied to the decimal digits of Pi...
Modelling Extinction of Polio Transmission Agents by Stochastic Differential Equations
Eradicating poliomyelitis has been a major health concern to stakeholders the world over. In this study, we have developed a pair of stochastic equations for the extinction probability functions in two types of human tra...
How many interchanges does the selection sort make for iid geometric(p) input?
The note derives an expression for the number of interchanges made by selection sort when the sorting elements are iid variates from geometric distribution. Empirical results reveal we can work with a simpler model compa...