ALCOMFT-TR-01-171

Lars Arge and Jakob Pagter
I/O-Space Trade-Offs
Århus. Work packages 1 and 4. June 2001.

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.

Postscript file: ALCOMFT-TR-01-171.ps.gz (92 kb).