Abstract Lower Bounds for External Algebraic Decision Trees ∗

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 m n, N}) lower bound for both problems in a less restrictive model, which requires only that the worstcase internal-memory computation time is finite. Standard reductions immediately generalize these lower bounds to a large number of fundamental computational geometry problems.