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.
Users
Please
log in to take part in the discussion (add own reviews or comments).