%0 Journal Article %1 jiang00 %A Jiang, Tao %A Li, Ming %A Vitányi, Paul %C New York, NY, USA %D 2000 %I ACM %J J. ACM %K algorithm shellsort sorting %N 5 %P 905--911 %R 10.1145/355483.355488 %T A Lower Bound on the Average-case Complexity of Shellsort %V 47 %X We demonstrate an $O(pn1+1/p)$ lower bound on the average-case running time (uniform distribution) of p-pass Shellsort. This is the first nontrivial general lower bound for average-case Shellsort.

@article{jiang00, abstract = {We demonstrate an $O(pn1+1/p)$ lower bound on the average-case running time (uniform distribution) of p-pass Shellsort. This is the first nontrivial general lower bound for average-case Shellsort.}, acmid = {355488}, added-at = {2016-11-08T04:35:15.000+0100}, address = {New York, NY, USA}, author = {Jiang, Tao and Li, Ming and Vit\'{a}nyi, Paul}, biburl = {https://www.bibsonomy.org/bibtex/2969416699af7b855cab91bcbc1793e70/ytyoun}, doi = {10.1145/355483.355488}, interhash = {0c4831835f550150a3b937743f692999}, intrahash = {969416699af7b855cab91bcbc1793e70}, issn = {0004-5411}, issue_date = {Sept. 2000}, journal = {J. ACM}, keywords = {algorithm shellsort sorting}, month = sep, number = 5, numpages = {7}, pages = {905--911}, publisher = {ACM}, timestamp = {2016-11-08T08:47:54.000+0100}, title = {A Lower Bound on the Average-case Complexity of {Shellsort}}, volume = 47, year = 2000 }