A General Lower Bound on the I/O-Complexity of Comparison-based Algorithms

Authors

  • Lars Arge
  • Mikael Knudsen
  • Kirsten Larsen

DOI:

https://doi.org/10.7146/dpb.v21i407.6641

Abstract

We show a relationship between the number of comparisons and the number of I/O operations needed to solve a given problem. We work in a model, where the permitted operations are l/O-operations and comparisons of two records in internal memory. An I/O- operation swaps B records between external memory and the internal memory (capable of holding M records). An algorithm for this model is called an I/O-algorithm. The main result of this paper is the following: Given an I/O-algorithm that solves an n-record problem P_n using I/O(bar{x}) I/O's on the input bar{x}, there exists an ordinary comparison algorithm that uses no more than n logB + I/O(bar{x}) € T_{merge}(M-B, B) comparisons on input bar{x}. T_{merge}(n, m) denotes the number of comparisons needed to merge two sorted lists of size n and m, respectively. We use the result to show lower bounds on the number of I/O-operations needed to solve the problems of sorting, removing duplicates from a multiset and determining the mode (the most frequently occurring element in a multiset). Aggarwal and Vitter have shown that the sorting bound is tight. We show the same result for the two other problems, by providing optimal algorithms.

Author Biographies

Lars Arge

Mikael Knudsen

Kirsten Larsen

Downloads

Published

1992-08-01

How to Cite

Arge, L., Knudsen, M., & Larsen, K. (1992). A General Lower Bound on the I/O-Complexity of Comparison-based Algorithms. DAIMI Report Series, 21(407). https://doi.org/10.7146/dpb.v21i407.6641