<p>Let $G$ be a linear time (deterministic) turing machine that takes positive integers $n$ in unary to lists of length $n.$ For any fixed such $G$, define sparse-sort(G,n) as the problem of sorting the list that $G$ outputs for input size $n$.</p>

<p>In general, can we compute sparse-sort(G,n) asymptotically faster than $O(n \log n)$?</p>

<hr>

<p>It's easy to generate examples where we can manage linear time, for example any $G$ that runs $G(n-1)$, then appends some predictable value to the list. Likewise, it seems plausible that one could use the function $G$ in the algorithm to get a good runtime in general.</p>

CC BY-SA 3.0
2017-09-26T15:55:23.623Z
It depends a bit on what you mean - if you only count comparisons then, according to your definition there is a unique output for every n, which means that there exists an algorithm that doesn't use any comparisons at all... but I'm guessing that wasn't what you meant - so there has to be some reasonable reformulation of the model here.
daniello
CC BY-SA 3.0
2017-09-26T16:50:33.843Z
I'd like an algorithm that runs for every pair $G \times n$, or perhaps for a fixed $G$ and every $n$. We can't memorize the output for every $n$, the table is too big!
Artimis Fowl
CC BY-SA 3.0
2017-09-27T14:38:17.943Z
@MarzioDeBiasi the output of G should be a list of length $n$ of any integers in a reasonable format. Not necessarily $[n]$ to avoid radix sort answers, and probably not in unary because that usually takes longer than $O(n)$ time to write.
Artimis Fowl
CC BY-SA 3.0
2017-09-27T14:39:45.670Z
Ok! Now it's clear!
Marzio De Biasi
<turing-machines><sorting>
How fast can we sort a list if we know how it was written?
Artimis Fowl
# How fast can we sort a list if we know how it was written?

(Asked by: username_0 on 2017-09-26)

Let $G$ be a linear time (deterministic) turing machine that takes positive integers $n$ in unary to lists of length $n.$ For any fixed such $G$, define sparse-sort(G,n) as the problem of sorting the list that $G$ outputs for input size $n$.

In general, can we compute sparse-sort(G,n) asymptotically faster than $O(n \log n)$?

---

It's easy to generate examples where we can manage linear time, for example any $G$ that runs $G(n-1)$, then appends some predictable value to the list. Likewise, it seems plausible that one could use the function $G$ in the algorithm to get a good runtime in general.

**Tags:** turing-machines, sorting

> **Comments:**
> **username_1**: It depends a bit on what you mean - if you only count comparisons then, according to your definition there is a unique output for every n, which means that there exists an algorithm that doesn't use any comparisons at all... but I'm guessing that wasn't what you meant - so there has to be some reasonable reformulation of the model here.  
> **username_0**: I'd like an algorithm that runs for every pair $G \times n$, or perhaps for a fixed $G$ and every $n$. We can't memorize the output for every $n$, the table is too big!  
> **username_0**: @MarzioDeBiasi the output of G should be a list of length $n$ of any integers in a reasonable format. Not necessarily $[n]$ to avoid radix sort answers, and probably not in unary because that usually takes longer than $O(n)$ time to write.  
> **username_2**: Ok! Now it's clear!  

---

## 0 answers

