On a standard computing model that reflects reality for sequential processing, such as a RAM machine with penalized access time for growing memory, can a comparison sort algorithm work in both logspace yet sub-quadratic time?

Standard algorithms for sorting are O(n*log(n)) time yet I've found that once these programs are restricted to only read-only input, write-only output, and pointers for indexing into the I/O, they seem to suddenly require quadratic time.

Another question on cstheory prompted answers giving model-independent lower bounds for famous complexity classes such as NP requiring a product of time and space resources to be nearly quadratic. Does that same argument apply here to non-trivial problems in L?

  • $\begingroup$ Can you clarify the computational model you have in mind? What's "penalized access time for growing memory"? Are we allowed to assume there is read-write temporary space available, of size comparable to the size of the input? If not, how much temporary/scratch space is available, as a function of $n$? Are you asking what is the best possible running time for a comparison-based sorting algorithm with $O(\log n)$ space, read-only input, and write-only output? $\endgroup$ – D.W. Apr 24 '17 at 23:34
  • 1
    $\begingroup$ Related: cstheory.stackexchange.com/q/4556/5038, cstheory.stackexchange.com/q/832/5038. Lower bounds for element distinctness presumably imply lower bounds for sorting, from which it appears we can infer that any algorithm must have $\Omega(n^{1.5}/\log n)$ running time. Another lower bound is apparently $\Omega(n^{2-\epsilon}/\log n)$ where $\epsilon = O(1/\sqrt{\log n})$. $\endgroup$ – D.W. Apr 24 '17 at 23:44

The following paper proves that any comparison-based sorting algorithm must satisfy $TS = \Omega(n^2)$, where $T$ is the running time and $S$ is the amount of read-write space used.

Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, Martin Tompa. A Time-Space Tradeoff for Sorting on Non-Oblivious Machines. Journal of Computer and System Sciences, vol 22 pp.351--364, 1981.

In particular, if $S = O(\log n)$, then $T = \Omega(n^2/\log n)$, i.e., if you have only logarithmic space, then the running time has to be nearly quadratic.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy