Optimal time-space trade-offs for non-comparison-based sorting

ABSTRACT

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 Θ(n²). 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(n²/T + w), which is optimal. Given a deterministic priority queue using amortized time t(n) per operation and space n^O(1), we provide a deterministic algorithm sorting in time T = O(n(t(n) + lg* n)) with S = O(n²/T + w). Both results require that w ≤ n^1-Ω(1). Using existing priority queues and sorting algorithms, this implies that we can deterministically sort time-space optimally in time Θ(T) for T ≥ n(lg lg n)², and with high probability for T ≥ nlg lg n.Our results imply that recent space lower bounds for deciding element distinctness in o(nlgn) time are nearly tight.

REFERENCES

• 1: Karl Abrahamson, Time-space tradeoffs for algebraic problems on general sequential machines, Journal of Computer and System Sciences, v.43 n.2, p.269-289, Oct. 1991 [doi>10.1016/0022-0000(91)90014-V]
• 2: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 3: Miklos Ajtai, A Non-Linear Time Lower Bound for Boolean Branching Programs, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.60, October 17-18, 1999
• 4: Miklós Ajtai, Determinism versus non-determinism for linear time RAMs (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.632-641, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301424]
• 5: Arne Andersson, Sorting and Searching Revisted, Proceedings of the 5th Scandinavian Workshop on Algorithm Theory, p.185-197, July 03-05, 1996
• 6: Arne Andersson , Torben Hagerup , Stefan Nilsson , Rajeev Raman, Sorting in linear time?, Journal of Computer and System Sciences, v.57 n.1, p.74-93, Aug. 1998 [doi>10.1006/jcss.1998.1580]
• 7: Lars Arge, I/O-Space Trade-Offs, Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, p.448-461, July 05-07, 2000
• 8: Paul Beame, A general sequential time-space tradeoff for finding unique elements, SIAM Journal on Computing, v.20 n.2, p.270-277, April 1990 [doi>10.1137/0220017]
• 9: P. Beame , M. Saks , Xiaodong Sun , E. Vee, Super-linear time-space tradeoff lower bounds for randomized computation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.169, November 12-14, 2000
• 10: Paul Beame , Michael Saks , Jayram S. Thathachar, Time-Space Tradeoffs for Branching Programs, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.254, November 08-11, 1998
• 11: Allan Borodin and Stephen Cook. A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation. SIAM Journal on Computing, 11(2):287-297, 1982.
• 12: A. Borodin , F. Fich , F. Meyer auf der Heide , E. Upfal , A. Wigderson, A time-space tradeoff for element distinctness, SIAM Journal on Computing, v.16 n.1, p.97-99, Feb. 1987 [doi>10.1137/0216007]
• 13: Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, and Martin Tompa. A Time-Space Tradeoff for Sorting on Non-Oblivious Machines. Journal of Computer and System Sciences, 22:351-364, 1981.
• 14: J. Lawrence Carter , Mark N. Wegman, Universal classes of hash functions (Extended Abstract), Proceedings of the ninth annual ACM symposium on Theory of computing, p.106-112, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803400]
• 15: Alan Cobham. The Recognition Problem for the Set of Perfect Squares. In Conference Record of the 7th Annual Symposium on Switching and Automata Theory, pages 78-87. IEEE, 1966.
• 16: Martin Dietzfelbinger , Joseph Gil , Yossi Matias , Nicholas Pippenger, Polynomial Hash Functions Are Reliable (Extended Abstract), Proceedings of the 19th International Colloquium on Automata, Languages and Programming, p.235-246, July 13-17, 1992
• 17: Greg N. Frederickson, Upper bounds for time-space trade-offs in sorting and selection, Journal of Computer and System Sciences, v.34 n.1, p.19-26, Feb. 1987 [doi>10.1016/0022-0000(87)90002-X]
• 18: Michael L. Fredman , Dan E. Willard, Surpassing the information theoretic bound with fusion trees, Journal of Computer and System Sciences, v.47 n.3, p.424-436, Dec. 1993 [doi>10.1016/0022-0000(93)90040-4]
• 19: Michael L. Fredman , Dan E. Willard, Trans-dichotomous algorithms for minimum spanning trees and shortest paths, Journal of Computer and System Sciences, v.48 n.3, p.533-551, June 1994 [doi>10.1016/S0022-0000(05)80064-9]
• 20: Torben Hagerup, Sorting and Searching on the Word RAM, Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, p.366-398, February 25-27, 1998
• 21: Yijie Han, Improved fast integer sorting in linear space, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.793-796, January 07-09, 2001, Washington, D.C., United States
• 22: J. Ian Munro and Mike S. Paterson. Selection and Sorting with Limited Storage. Theoretical Computer Science, 12:315-323, 1980.
• 23: Jakob Pagter. On Ajtai's Lower Bound Technique for R-way Branching Programs and the Hamming Distance Problem. BRICS Report RS-00-11, Department of Computer Science, University of Aarhus, 2000.
• 24: Jakob Pagter , Theis Rauhe, Optimal Time-Space Trade-Offs for Sorting, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.264, November 08-11, 1998
• 25: Mikkel Thorup, On RAM Priority Queues, SIAM Journal on Computing, v.30 n.1, p.86-109, 2000 [doi>10.1137/S0097539795288246]
• 26: Mikkel Thorup, Faster deterministic sorting and priority queues in linear space, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.550-555, January 25-27, 1998, San Francisco, California, United States
• 27: Dan E. Willard, Examining Computational Geometry, Van Emde Boas Trees, and Hashing from the Perspective of the Fusion Tree, SIAM Journal on Computing, v.29 n.3, p.1030-1049, Dec. 1999 to Jan. 2000 [doi>10.1137/S0097539797322425]
• 28: Andrew Chi-Chih Yao. Probabilistic computations: toward a unified measure of complexity (extended abstract). In Proceedings of the 18th Annual Symposium on Foundations of Computer Science, pages 222-227. IEEE, 1977.
• 29: Andrew Chi-Chih Yao, Near-Optimal Time-Space Tradeoff for Element Distinctness, SIAM Journal on Computing, v.23 n.5, p.966-975, Oct. 1994 [doi>10.1137/S0097539788148959]