A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation

Abstract

In a general sequential model of computation, no restrictions are placed on the way in which the computation may proceed, except that parallel operations are not allowed. We show that in such an unrestricted environment ${\text{TIME}} \cdot {\text{SPACE}} = \Omega (N^2 /\log N)$ in order to sort N integers, each in the range $[1,N^2 ]$.