Asymptotic estimates for the higher moments of the expected behavior of straight insertion sort (Q790618)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Asymptotic estimates for the higher moments of the expected behavior of straight insertion sort |
scientific article |
Statements
Asymptotic estimates for the higher moments of the expected behavior of straight insertion sort (English)
0 references
1982
0 references
The author studies the complexity of one of the simplest sorting algorithms -- straight insertion sort. The number of executions of the while-loop in the algorithm, \(W(n)\) (where \(n\) is the number of elements to be sorted) is analysed as a random variable, whose \(k\)-th moment, \(W(n,k)\) is asymptotically estimated, by turns, for \(k\to \infty\) and for \(n\to \infty\). \(W(n,k)\) is explicitly represented by means of Bernoulli numbers; fixing \(k\), the major term giving the asymptotic estimation of \(W(n,k)\) is found to be \((\frac n2)^{2k}\).
0 references
insertion sort
0 references
average case analysis
0 references
higher moments
0 references
Bernoulli numbers
0 references