TY - JOUR
AU - Pagh, Rasmus
AU - Pagter, Jakob
PY - 2001/01/02
Y2 - 2024/02/25
TI - Optimal Time-Space Trade-Offs for Non-Comparison-Based Sorting
JF - BRICS Report Series
JA - BRICS
VL - 8
IS - 2
SE - Articles
DO - 10.7146/brics.v8i2.20456
UR - https://tidsskrift.dk/brics/article/view/20456
SP -
AB - <p>We study the fundamental 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 Theta(n^2). 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 <br />Omega(n lg n) lower bound. </p><p>We show that if sorting within some time bound T~ is possible, then time T = O(T~ + n lg* n) can be achieved with high probability using space S = O(n^2/T + w), which is optimal. Given a deterministic priority queue using amortized<br />time t(n) per operation and space n^O(1), we provide a deterministic<br />algorithm sorting in time T = O(n (t(n) + lg* n)) with S = O(n^2/T+w). Both results require that w <= n^(1-Omega(1)).</p><p>Using existing priority queues and sorting algorithms, this implies<br />that we can deterministically sort time-space optimally in time Theta(T) for T >= n(lg lg n)^2, and with high probability for T >= n lg lg n.</p><p>Our results imply that recent lower bounds for deciding element distinctness in o(n lg n) time are nearly tight.</p>
ER -