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.

  • 1
    $\begingroup$ 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. $\endgroup$ – daniello Sep 26 '17 at 15:55
  • $\begingroup$ 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! $\endgroup$ – Artimis Fowl Sep 26 '17 at 16:50
  • $\begingroup$ @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. $\endgroup$ – Artimis Fowl Sep 27 '17 at 14:38
  • $\begingroup$ Ok! Now it's clear! $\endgroup$ – Marzio De Biasi Sep 27 '17 at 14:39

Your Answer

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

Browse other questions tagged or ask your own question.