62 citations · 63 across the 4 of their papers we have counts for
Showing cs.DSShow all
2 papers · 1 filter
cs.DS1999
Mutual Search
Harry Buhrman, Matthew Franklin, Juan A. Garay +3
We introduce a search problem called ``mutual search'' where \agents, arbitrarily distributed over sites, are required to locate one another by posing queries of the form `…
cs.DS1999
Average-Case Complexity of Shellsort
Tao Jiang, Ming Li, Paul Vitanyi
We prove a general lower bound on the average-case complexity of Shellsort: the average number of data-movements (and comparisons) made by a -pass Shellsort for any incremental…