6
$\begingroup$

If we consider literature, sorting algorithms are based only on number of comparisons needed to sort a list of size n, considering that n is the size of the input.

But if we want to encode input, we can't encode each object of the list into a fixed-size binary representation because hence, we would consider that the domain of the objects is fixed and thus, I think we could find better sorting algorithms by precomputing some stuff in the Turing Machine.

If we consider that the domain isn't fixed, we have to encode each of our items into a $\log(n)$-size representation. Thus the input is of size $N = n\log(n)$. But as our numbers are of variable length, then we can consider that comparison has a cost of $\log(n)$, but even with this, if we apply a reasonable sorting algorithm (ie an $n \log n$ algorithm), the algorithm will take $n \log^2(n)$ time in a Turing machine, where $n$ is the number of objects, but where $n \log n$ is the size of our input. In this case, we have an algorithm of complexity lower than $O(N \log(N))$ where $N$ is the size of the input.

Is there a mistake?

Improve this question
$\endgroup$

5 Answers 5

Reset to default
10
$\begingroup$

Without looking at any details, why do your say your algorithm beats $O(N\log N)$?

In your notation, $N\log N = n\log n\log(n\log n) = n\log n\log n + n\log n\log\log n = O(n\log^2n)$.

No contradiction.

Improve this answer
$\endgroup$
4
  • $\begingroup$ That's true, sorry. But couldn't we try to use the fact that comparisons are bitwise to try to "group" them by any way even if the order of the objects isn't the same as the order induced by the binary representation ? $\endgroup$
    – Ludovic Patey
    Oct 14, 2010 at 20:54
  • $\begingroup$ I'm not sure what you mean. $\endgroup$
    – Lev Reyzin ♦
    Oct 14, 2010 at 21:15
  • $\begingroup$ All I mean is that as comparisons are in log n, they aren't in one step, and thus substeps could be mutualised between comparisons and so reduce their number. $\endgroup$
    – Ludovic Patey
    Oct 14, 2010 at 21:28
  • $\begingroup$ Often, the O(nlogn) lower bounds assume an input of size n and unit comparison costs. In that case there's nothing to play with. In general, even if you're counting bits, I doubt you can win much. $\endgroup$
    – Lev Reyzin ♦
    Oct 15, 2010 at 12:20
8
$\begingroup$

Generally speaking, you can sort n numbers where each is given by O(log n) bits using time that is linear in the input size (i.e. O(nlogn)) using something like radix sort (but you may need to be careful about the exact model of computation -- and I don't know the details of which models admit such linear time algorithms).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Which models admit fast algorithms seems like a question where there may not be consensus: blog.computationalcomplexity.org/2009/05/… $\endgroup$
    – Aaron Sterling
    Oct 14, 2010 at 21:39
  • $\begingroup$ Maybe, but as I said to Charles, those kind of algorithms use meta information about the input. There, the fact that they are numbers. I was looking for a general sort algorithm, ie without other information than the comparison function. $\endgroup$
    – Ludovic Patey
    Oct 14, 2010 at 21:42
5
$\begingroup$

There are many examples of $o(n\log n)$ sorting in the literature. For example,

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I think all algorithms known in < n log n cheat by using meta informations on the input list, or it isn't complexity in the worst case. $\endgroup$
    – Ludovic Patey
    Oct 14, 2010 at 20:57
  • 2
    $\begingroup$ These solve more restricted problems than a general comparison sort does and are thus able to go faster. No comparison sort can exceed lg(n!) = Omega(n log n) in the worst case. $\endgroup$
    – Charles
    Oct 14, 2010 at 22:54
3
$\begingroup$

I think you are confusing the size of the input with the number of elements in the input. The time complexity of sorting algorithms is defined in terms of the number of comparisons based on the number of elements, not on the size of the inputs, so when you say that it costs $n \log^2 n$ to sort the elements you are already saying that your algorithm is worst than $O(n\log n)$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It was the purpose of my question : the difference of size between input and the number of elements which could make complexity lower than O(n log n) in complexity theory. $\endgroup$
    – Ludovic Patey
    Oct 15, 2010 at 14:26
3
$\begingroup$

Another example is Fredman and Willard (1993), Surpassing the information theoretic bound with fusion trees.

Improve this answer
$\endgroup$

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.

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