I/O complexity
Jiawei Hong, H. T. Kung · 1981
In this paper, the red-blue pebble game is proposed to model the input-output complexity of algorithms. Using the pebble game formulation, a number of lower bound results for the I/O requirement are proven. For example, it is shown that to perform the n-point FFT or the ordinary n×n matrix multiplication algorithm with O(S) memory, at least Ω(n log n/log S) or Ω(n3/@@@@S), respectively, time is needed for the I/O. Similar results are obtained for algorithms for several other problems. All of the lower bounds presented are the best possible in the sense that they are achievable by certain decomposition schemes.
Cited by 447 works. doi:10.1145/800076.802486
Authors
References
- Graph theory
- The Art of Computer Programming: Volume 3: Sorting and Searching
- An Efficient Heuristic Procedure for Partitioning Graphs
- On Time Versus Space
- Permuting Information in Idealized Two-Level Storage
- Storage requirements for deterministic polynomialtime recognizable languages
- Special-purpose devices for signal and image processing : an opportunity in VLSI