Asymptotic estimates for the higher moments of the expected behavior of straight insertion sort (Q790618)

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}\).