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 140
- Downloads 0
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...
An In-depth Study of Typical Machine Learning Methods via Computational Techniques
The ability to model and perform decision modeling and analysis is an essential feature of many real-world applications ranging from emergency medical treatment in intensive care units to military command and control sys...
Mathematical Analysis of Blood Flow through a Stenosed Human Artery
This paper examines the mathematical analysis of blood flow through a stenosed human artery. Change in the nature of blood flow from its normal state to a disturbed flow condition due to the presence of stenoses in the h...
Modelling Queuing System with Inverse Gamma Distribution: A Spreedsheet Simulation Approach
There is a need to provide user friendly approach to modeling and simulation for learners and business modeler. This study offers process-driven queuing simulation via spreadsheet which provides a user friendly, yet a re...
Prediction of Skin Disease using Decision Tree and Artificial Neural Network (ANN)
Skin diseases are common diseases that exist between the children and adults in the society. The issue of finding and proffering a better skin disease predictive model in the health care system has been identified to be...