Name
Abstract | ||
|---|---|---|
We prove a general lower bound on the average-case com- plexity of Shellsort: the average number of data-movements (and com- parisons) made by a p-pass Shellsort for any incremental sequence is (pn1+1/p) for every p. The proof method is an incompressibility ar- gument based on Kolmogorov complexity. Using similar techniques, the average-case complexity of several other sorting algorithms is analyzed. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1007/3-540-48523-6_42 | international colloquium on automata, languages and programming |
Keywords | Field | DocType |
lower bound,data structure,sorting algorithm,computational complexity | Discrete mathematics,Average-case complexity,Combinatorics,Kolmogorov complexity,Upper and lower bounds,Binary strings,Shellsort,Young tableau,Sorting algorithm,Mathematics | Journal |
Volume | Citations | PageRank |
cs.CC/9906 | 6 | 0.46 |
References | Authors | |
8 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tao Jiang | 1 | 366 | 33.90 |
| Ming Li | 2 | 5595 | 829.00 |
| Paul Vitányi | 3 | 2130 | 287.76 |