5 ms·

This is not "linear time" in any decent sense--we shouldn't conflate the number of elements with the size of the elements (in this case, O(max element) is actua

This is not "linear time" in any decent sense--we shouldn't conflate the number of elements with the size of the elements (in this case, O(max element) is actually exponential in the input size!).

duaneb 12y ago
Yea, it's linear time for n where n is the largest number—pretty sure it's unbounded in terms of numbers of elements.
- bnegreve 12y ago
  True, but writing a linear sort with bounded number of distinct elements is not really a challenge. E.g. Intput, T: array of n elements, m: number of distinct elements. for i in 1..m for j in 1..n if( T[j] == i ) print T[j]; This is O(n * m) which is O(n) since m is a constant.
asdfaoeu 12y ago
the max size of the elements is usually constant when comparing sorting algorithms. The complexity of this depends on the algorithm of the scheduler. With the right scheduler this could be O(nlog n).
antics 12y ago
This isn't really right. If the numbers can be arbitrary in size, then you can't compare them in constant time, which means that comparison-based sorts are quadratic. This is directly related to my third point. Traditional analysis of sorting algorithms assumes the Von Neumann architecture, and in particular, it assumes constant-time comparisons.
- flebron 12y ago
  The computational model will define what you can and cannot compare in constant time. It is perfectly fine to say that comparing elements of arbitrary size is a constant time operation - that's precisely what a computational model is: an enumeration of the operations that are considered basic.
  - antics 12y ago
    Yeah, I know. Go read the parent again. The author claims that sorting in this case takes time proportional to the size of largest element, and I'm saying, if it takes time proportional to the space consumption of in the largest element (presumably where the cost of the sort comes from), you can't define a computational model where comparison takes constant time -- it still has to read the digits, which we know takes linear time. If your point is that you can define a model of computation with contradictions in it, then you should rethink whether what you are saying here is even relevant to the thread at all.
    - Retric 12y ago
      You can shurt circuit comparisons but that's not always going to happen. Consider it's completly reasonable to assume long int is sorted as fast as int on a 128 bit CPU. If nothing else it's useful to have a fairly long cycle even if you could in theory use a 20GHz CPU that has some comparisons finish in 4 cycles and others just 1. Sure, it might be slightly faster than a 5GHz CPU with constant time comparisons, but the added complexity is not free.
      - antics 12y ago
        I am not sure I understand your point here. Short circuiting comparisons is still linear for integers of unbounded size. But besides that, it's incredibly common to assume that 64-bit primitives are done in constant time, because to the asymptotic analysis, what matters is that the integers are _bounded_ in size. As long as it's bounded, the asymptotic analysis here doesn't care -- you can pick any size you want, as long as it's bounded. One thing to keep in mind here (which it seems you are maybe confused about) is that these bounds are _asymptotics_ of the input size generally, and have very little to say about any particular choice of input size. 64-bit, 32-bit, whatever, it doesn't matter, if the size of the operands is bounded, the they're the same thing to the asymptotic analysis. As long as they're bounded, you can say that the operations on those operands is proportional to a constant times the (bounded) size of the operands. The consequence of this is that when you deal with operands of _unbounded_ size, all of this asymptotic analysis goes right out the window. You can't possibly have a meaningful comparison operator, for example, that operates in constant time on unbounded integers.
SilasX 12y ago
I thought that too, but couldn't you make element size irrelevant by renormalizing the list? One pass to find the max, one pass to divide everything by it.

This is not "linear time" in any decent sense--we shouldn't conflate the number of elements with the size of the elements (in this case, O(max element) is actually exponential in the input size!).

duaneb 12y ago

Yea, it's linear time for n where n is the largest number—pretty sure it's unbounded in terms of numbers of elements.

bnegreve 12y ago
True, but writing a linear sort with bounded number of distinct elements is not really a challenge. E.g. Intput, T: array of n elements, m: number of distinct elements. for i in 1..m for j in 1..n if( T[j] == i ) print T[j]; This is O(n * m) which is O(n) since m is a constant.

asdfaoeu 12y ago

the max size of the elements is usually constant when comparing sorting algorithms. The complexity of this depends on the algorithm of the scheduler. With the right scheduler this could be O(nlog n).

antics 12y ago

This isn't really right. If the numbers can be arbitrary in size, then you can't compare them in constant time, which means that comparison-based sorts are quadratic. This is directly related to my third point. Traditional analysis of sorting algorithms assumes the Von Neumann architecture, and in particular, it assumes constant-time comparisons.

flebron 12y ago
The computational model will define what you can and cannot compare in constant time. It is perfectly fine to say that comparing elements of arbitrary size is a constant time operation - that's precisely what a computational model is: an enumeration of the operations that are considered basic.
- antics 12y ago
  Yeah, I know. Go read the parent again. The author claims that sorting in this case takes time proportional to the size of largest element, and I'm saying, if it takes time proportional to the space consumption of in the largest element (presumably where the cost of the sort comes from), you can't define a computational model where comparison takes constant time -- it still has to read the digits, which we know takes linear time. If your point is that you can define a model of computation with contradictions in it, then you should rethink whether what you are saying here is even relevant to the thread at all.
  - Retric 12y ago
    You can shurt circuit comparisons but that's not always going to happen. Consider it's completly reasonable to assume long int is sorted as fast as int on a 128 bit CPU. If nothing else it's useful to have a fairly long cycle even if you could in theory use a 20GHz CPU that has some comparisons finish in 4 cycles and others just 1. Sure, it might be slightly faster than a 5GHz CPU with constant time comparisons, but the added complexity is not free.
    - antics 12y ago
      I am not sure I understand your point here. Short circuiting comparisons is still linear for integers of unbounded size. But besides that, it's incredibly common to assume that 64-bit primitives are done in constant time, because to the asymptotic analysis, what matters is that the integers are _bounded_ in size. As long as it's bounded, the asymptotic analysis here doesn't care -- you can pick any size you want, as long as it's bounded. One thing to keep in mind here (which it seems you are maybe confused about) is that these bounds are _asymptotics_ of the input size generally, and have very little to say about any particular choice of input size. 64-bit, 32-bit, whatever, it doesn't matter, if the size of the operands is bounded, the they're the same thing to the asymptotic analysis. As long as they're bounded, you can say that the operations on those operands is proportional to a constant times the (bounded) size of the operands. The consequence of this is that when you deal with operands of _unbounded_ size, all of this asymptotic analysis goes right out the window. You can't possibly have a meaningful comparison operator, for example, that operates in constant time on unbounded integers.

SilasX 12y ago

I thought that too, but couldn't you make element size irrelevant by renormalizing the list? One pass to find the max, one pass to divide everything by it.