Asymptotic estimates for the higher moments of the expected behavior of straight insertion sort (Q790618): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Asymptotic Methods in Enumeration / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Continuous models that are equivalent to randomness for the analysis of many sorting algorithms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5541610 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4057549 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3243274 / rank | |||
Normal rank |
Latest revision as of 12:12, 14 June 2024
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
0 references