Upper bounds for time-space trade-offs in sorting and selection (Q1101238)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Upper bounds for time-space trade-offs in sorting and selection |
scientific article |
Statements
Upper bounds for time-space trade-offs in sorting and selection (English)
0 references
1987
0 references
Upper bound time-space trade-offs are established for sorting and selection in two computational models. For machines with input in read- only random access registers, and for machines with input on a read-only tape, we present algorithms that realize trade-offs of \(T\cdot S=O(N^ 2)\) for sorting and T log S\(=O(N \log N)\) for selection, where S is the number of workspace registers.
0 references
time-space trade-offs
0 references
sorting
0 references
selection
0 references
computational models
0 references