𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Average time behavior of distributive sorting algorithms

✍ Scribed by L. Devroye; T. Klincsek

Publisher
Springer Vienna
Year
1981
Tongue
English
Weight
284 KB
Volume
26
Category
Article
ISSN
0010-485X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A time-optimal distributed sorting algor
A time-optimal distributed sorting algorithm on a line network
✍ Atsushi Sasaki πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 87 KB

We have achieved a strict lower time bound of n -1 for distributed sorting on a line network, where n is the number of processes. The lower time bound has traditionally been considered to be n because it is proved based on the number of disjoint comparison-exchange operations in parallel sorting on

On the Average Running Time of Odd–Even
On the Average Running Time of Odd–Even Merge Sort
✍ Christine RΓΌb πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 178 KB

This paper gives an upper bound for the average running time of Batcher's odd᎐even merge sort when implemented on a collection of processors. We consider the case where n, the size of the input, is an arbitrary multiple of the number Ž p of processors used. We show that Batcher's odd᎐even merge for

Drift analysis and average time complexi
Drift analysis and average time complexity of evolutionary algorithms
✍ Jun He; Xin Yao πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 212 KB

The computational time complexity is an important topic in the theory of evolutionary algorithms (EAs). This paper reports some new results on the average time complexity of EAs. Based on drift analysis, some useful drift conditions for deriving the time complexity of EAs are studied, including cond