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 122
- Downloads 0
Manual and Fast C Code Optimization
Developing an application with high performance through the code optimization places a greater responsibility on the programmers. While most of the existing compilers attempt to automatically optimize the program code, m...
Analytic Approach To Face Emotion Recognition With SVM Kernels
Face emotion recognition is one of the challenges known with emotion recognition and it has received much attention during the recent years due to its application in different fields. SVM kernels were adopted to increase...
How does the Shift-insertion sort behave when the sorting elements follow a Normal distribution?
The present paper examines the behavior of Shift-insertion sort (insertion sort with shifting) for normal distribution inputs and is in continuation of our earlier work on this new algorithm for discrete distribution inp...
e-HAMS: A Unified Model-based Integrated Healthcare Services Management System for Low-and-Middle Income Economies
The emerging proliferation of fragmented healthcare applications has accounted for an overwhelming high cost of maintaining healthcare services and facilities, clinical data security and privacy concerns, decentralized d...
Modelling of Enugu State Monthly Rainfall using Box and Jenkins Methodology
The paper examined the rainfall distribution of Enugu state in Nigeria. Box-Jenkins methodology was used to build ARIMA model to analyze data and forecast for the period of 15 years, from January, 2002 to December, 2016...