|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article forum
| |
|
|
Average-Case Complexity of Shellsort (Preliminary version) | | Tao Jiang
; Ming Li
; Paul Vitanyi
; | | Date: |
4 Jun 1999 | | Subject: | Computational Complexity; Data Structures and Algorithms ACM-class: F.2.2, E.1 | cs.CC cs.DS | | Affiliation: | McMaster U.), Ming Li (U. Waterloo), Paul Vitanyi (CWI & U. Amsterdam | | Abstract: | We prove a general lower bound on the average-case complexity of Shellsort: the average number of data-movements (and comparisons) made by a $p$-pass Shellsort for any incremental sequence is $Omega (pn^{1 + 1/p})$ for every $p$. The proof method is an incompressibility argument based on Kolmogorov complexity. Using similar techniques, the average-case complexity of several other sorting algorithms is analyzed. | | Source: | arXiv, cs.CC/9906008 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No message found in this article forum.
You have a question or message about this article?
Ask the community and write a message in the forum.
If you want to rate this article, please use the review section..
To add a message in the forum, you need to login or register first. (free): registration page
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER