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 150
- Downloads 0
New Trends in Modelling Climate Change in the Era of Big Data
Big data is data sets that are so voluminous and complex that traditional data processing application software are inadequate to deal with. It is typically characterized by the so called, seven “V’s” namely; volume, velo...
Estimators in Cryptography
One of the main problems in cryptography is to give criteria to provide good comparators of cipher systems. The security of a cipher system must include the security of the algorithm, the security of the key generator an...
Performance Evaluation of Improved Cognitive Complexity Metric and Other Code Based Complexity Metrics
Complexity metric is used to estimate various parameters such as software development cost, amount of time needed for implementation and effort required in understanding the software. In this paper, different software co...
Mobile Students’ Academic Record Manager
With increasing ownership of smart phones and the prevalent use of mobile apps among the students, the necessity to develop mobile applications useful to assist students’ daily lives and academics arises. This study ther...
Prior Specification in Bayesian Model Averaging: An application to Economic Growth
Some recent cross-country cross-sectional analyses have employed Bayesian Model Averaging to tackle the issue of model uncertainty. Bayesian model averaging has become an important tool in empirical settings with large n...