A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
Allan Borodin, Stephen A Cook · SIAM Journal on Computing · 1982
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 ]$.