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
Arabic statistical modeling based on morphology
In this work we submit the results obtained for the building of a statistical model of the Arabic language, adopting for a word the prefix*-stem-suffix structure based on the lattice. That solution allowed us to keep all...
Algorithm Development for Mixture of Two Colors for Enhancement of New Color Development
Due to the problem that normally occur when colors are needed to be chosen for industrial uses, color are needed to be mixed together to generate new difference color. The algorithms were developed in two phases which co...
Password Authentication Scheme with Secured Login Interface
This paper presents a novel solution to the age long problem of password security at input level. In our solution, each of the various characters from which a password could be composed is encoded with a random single di...
XML Technologies in Computer Assisted Learning and Testing Systems
The learning and assessment activities have undergone major changes due to the development of modern technologies. The computer-assisted learning and testing has proven a number of advantages in the development of modern...
Parameterized Complexity on a New Sorting Algorithm: A Study in Simulation<br />
Sundararajan and Chakraborty (2007) introduced a new sorting algorithm by modifying the fast and popular Quick sort and removing the interchanges. In a subsequent empirical study, Sourabh, Sundararajan and Chakraborty (2...