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.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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...)
answered Feb 17 at 18:15
-
1$\begingroup$ That said, I was excited to see Jan's answer in a restricted model of TMs! $\endgroup$ Feb 17 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$– LouisFeb 20 at 9:20
$\begingroup$
$\endgroup$
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.
answered Feb 17 at 14:44