1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\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, 2017 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, 2017 at 23:44

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.