Empirical Study on the Robustness of Average Complexity & Parameterized Complexity Measure for Heapsort Algorithm

摘要

The present paper illustrates the average complexity (sorting time) when data comes from different distribution inputs using Heapsort Algorithm. The paper also examines the effects of parameters of the input distribution on the average case complexity for this algorithm. Average complexity measure O(n log n)for Heapsort seems to be robust. This was only expected since this algorithm has worst case complexity measure similar to that of average case and further that average complexity under universal distribution equals worst case complexity.rnRegarding parameterized complexity, average time in Heapsort seems to:rn1) be independent of p for Binomial (m, p) inputs. However there is a slight dependence on m.rn2) depend on the mean of Poisson distributionrn3) depend on the parameter k of discrete uniform [1,2,..., Ar] inputrn4) be independent of the parameter 9 of continuous uniform [0,θ] input.rn5) be independent of the parameter for exponential inputsrn6) depend only on mean but not variance for Normal inputs.