Abstract
We propose a natural extension of algebraic decision trees to the external-memory setting, where the cost of disk operations overwhelms CPU time, and prove a tight lower bound of Ω(n log m n) on the complexity of both sorting and element uniqueness in this model of computation. We also prove a Ω(min{n log mn, N}) lower bound for both problems in a less restrictive model, which requires only that the worst-case internal-memory computation time is finite. Standard reductions immediately generalize these lower bounds to a large number of fundamental computational geometry problems.
Original language | English (US) |
---|---|
Pages | 755-761 |
Number of pages | 7 |
State | Published - 2005 |
Event | Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States Duration: Jan 23 2005 → Jan 25 2005 |
Other
Other | Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|
Country/Territory | United States |
City | Vancouver, BC |
Period | 1/23/05 → 1/25/05 |
ASJC Scopus subject areas
- Software
- General Mathematics