Abstract: 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.
Publication Year: 1981
Publication Date: 1981-01-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 440
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot