5
$\begingroup$

Can we prove the lower bound for the sorting problem just by Turing machine model? It seems that available proof of sorting is based on the assumption that the algorithm only uses comparison so we can model it by decision tree and establish the lower bound of the number of comparisons.

$\endgroup$

2 Answers 2

3
$\begingroup$

If you are speaking specifically of sorting lists of integers on a multitape TM, then I think the answer is no. For example, comparison-based sorts, when implemented on a TM and sorting integers of bit-length $w$, take $\Theta(n w \log n)$ time, b/c it takes $\Theta(w)$ to compare two $w$-bit integers. But radix sort takes $O(nw)$ time, which is optimal as it is linear in the input size (assuming all the integers have the same number of bits).

See also fusion trees (but I think those are in the word RAM model and I'd have to carefully think through its translation to multitape TMs...)

$\endgroup$
2
  • 1
    $\begingroup$ That said, I was excited to see Jan's answer in a restricted model of TMs! $\endgroup$ Commented Feb 17, 2023 at 18:20
  • 1
    $\begingroup$ For the word RAM it depends on the exact variation of RAM you are using. But sorting n integers where the word length w is O(log(n)) takes times O(n) with a simple algorithm. For very large w (i.e. way bigger than log(n)) I think the question is open but you have a n × √log(log(n)) expected time and a n×log(log(n)) exact time one. [1] link.springer.com/article/10.1007/BF02127798 [2] ieeexplore.ieee.org/document/1181890 $\endgroup$
    – Louis
    Commented Feb 20, 2023 at 9:20
2
$\begingroup$

The paper "Sorting and Element Distinctness on One-Way Turing Machines" by Holger Petersen shows a lower bound for sorting on a Turing machine with one work tape and one-way input.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.