On the average‐case complexity of Shellsort. Issue 2 (13th November 2017)

• Record Type: Journal Article
• Authors: Vitányi, Paul
• Is Part Of: Random structures & algorithms. Volume 52:Issue 2(2018)
• Page Start: 354
• Page End: 363
• Publication Date: 2017-11-13
• Subjects: Shellsort -- average‐case complexity -- lower bound -- Kolmogorov complexity; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20737
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: 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.