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 155
- Downloads 0
Developing Predictive Models using Typical Machine Learning and Computational Techniques
This study investigates the accuracy of developing predictive models using machine learning techniques. The machine learning techniques considered in this study include artificial neural network (ANN) and Kalman filter a...
Variable Selection in the Modeling of Nigeria Economic Growth
This study aimed at identifying and retaining factors that contributed immensely to economic growth in Nigeria based on some variable selection methods. Stepwise regressions are often not efficient when there is multicol...
Proposition d’une méthode de qualification et de sélection d’un logiciel d’analyse et de suivi du référencement dans les moteurs de recherche
Reduction of enhanced maintenance effort using ARM model and RMMM plan
Software maintenance effort is playing a very important role for the development of the software. In maintenance phase user request for change and effort required for the maintenance of software is more as compare to the...
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...