Bit complexity of order statistics on a distributed star network (Q1116337)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Bit complexity of order statistics on a distributed star network |
scientific article |
Statements
Bit complexity of order statistics on a distributed star network (English)
0 references
1989
0 references
We study the bit complexity of order statistics problem on an asynchronous distributed star network. We prove a lower bound of \(\Omega\) (N log(LN)) bits for the k-selection problem, and lower bounds of \(\Omega\) (N log(L-N)) bits for the problems of sorting and ranking. For each of the problems we introduce an algorithm that achieves that bound, thus showing all bounds to be optimal.
0 references
bit complexity
0 references
order statistics
0 references
asynchronous distributed star network
0 references
lower bound
0 references
selection
0 references
sorting
0 references
ranking
0 references
