|
I/O-Space Trade-Offs
Lars Arge
April 2000 |
Abstract:
We define external memory (or I/O) models which capture space
complexity and develop a general technique for deriving I/O-space trade-offs
in these models from internal memory model time-space trade-offs. Using this
technique we show strong I/O-space product lower bounds for Sorting and
Element Distinctness. We also develop new space efficient external memory
Sorting algorithms
|