Average-Case Complexity of Shellsort
Tao Jiang, Ming Li, Paul Vitanyi
1999
We email you when a new notice or a question about this paper appears.
Abstract
We prove a general lower bound on the average-case complexity of Shellsort: the average number of data-movements (and comparisons) made by a $p$-pass Shellsort for any incremental sequence is $Ω(pn^{1 + 1/p)$ for all $p \leq \log n$. Using similar arguments, we analyze the average-case complexity of several other sorting algorithms.
Abstract licence: CC0
Reads
Read by people on this page
None yet.
Checked or read by AI through naulon
None yet.
A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.
Are you an author?
Is this your paper?
Claim it to add your note and be paid when agents cite it. Free.