Lower bounds for external algebraic decision trees

Research output: Contribution to conferencePaperpeer-review

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 languageEnglish (US)
Pages755-761
Number of pages7
StatePublished - Jul 1 2005
EventSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States
Duration: Jan 23 2005Jan 25 2005

Other

OtherSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityVancouver, BC
Period1/23/051/25/05

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Lower bounds for external algebraic decision trees'. Together they form a unique fingerprint.

Cite this