Aarhus University Seal

Optimal Time-Space Trade-Offs for Non-Comparison-Based Sorting

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearch

  • Rasmus Pagh, Denmark
  • Jacob Illeborg Pagter, Denmark
  • David Eppstein, University of California, United States
  • Department of Computer Science
We study the problem of sorting n integers of w bits on a unit-cost RAM with word size w, and in particular consider the time-space trade-off (product of time and space in bits) for this problem. For comparison-based algorithms, the time-space complexity is known to be Θ(n2). A result of Beame shows that the lower bound also holds for non-comparison-based algorithms, but no algorithm has met this for time below the comparison-based Ω(nlgn) lower bound.We show that if sorting within some time bound &Ttilde; is possible, then time T = O(&Ttilde; + nlg* n) can be achieved with high probability using space S = O(n2/T + w), which is optimal. Given a deterministic priority queue using amortized time t(n) per operation and space nO(1), we provide a deterministic algorithm sorting in time T = O(n(t(n) + lg* n)) with S = O(n2/T + w). Both results require that wn1-Ω(1). Using existing priority queues and sorting algorithms, this implies that we can deterministically sort time-space optimally in time Θ(T) for Tn(lg lg n)2, and with high probability for Tnlg lg n.Our results imply that recent space lower bounds for deciding element distinctness in o(nlgn) time are nearly tight.
Original languageEnglish
Title of host publicationSymposium on Discrete Algorithm : Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms
Number of pages10
PublisherAssociation for Computing Machinery
Publication year2002
ISBN (print)0-89871-513-X
Publication statusPublished - 2002
EventSODA '02, - San Francisco, California, United States
Duration: 6 Jan 20028 Jan 2002
Conference number: 13


ConferenceSODA '02,
LandUnited States
BySan Francisco, California

See relations at Aarhus University Citationformats

ID: 283275