Premium
On the average‐case complexity of Shellsort
Author(s) -
Vitányi Paul
Publication year - 2018
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20737
Subject(s) - upper and lower bounds , sequence (biology) , mathematics , combinatorics , computational complexity theory , discrete mathematics , algorithm , chemistry , mathematical analysis , biochemistry
We prove a lower bound expressed in the increment sequence on the average‐case complexity of the number of inversions of Shellsort. This lower bound is sharp in every case where it could be checked. A special case of this lower bound yields the general Jiang‐Li‐Vitányi lower bound. We obtain new results, for example, determining the average‐case complexity precisely in the Yao‐Janson‐Knuth 3‐pass case.