Bit complexity of order statistics on a distributed star network (Q1116337)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4088929
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Bit complexity of order statistics on a distributed star network |
scientific article; zbMATH DE number 4088929 |
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
0.8707885
0 references
0.85829204
0 references
0.85434955
0 references
0.85434955
0 references
0.84253716
0 references
0.8401897
0 references
0.8401897
0 references
0.8336164
0 references
