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.
Users
Please
log in to take part in the discussion (add own reviews or comments).