I am reading (Cormen) on counting sort.
I understand the structure of the algorithm but the statement:

In practice, we usually use counting sort when we have k = O(n), in which case the running time is Theta(n).

Is not clear to my mind.

k is just the range of integers expected in the input.

Why is the asymptotic notation used in this statement for k? I don't get it.


Your quote is saying that if the range of integers k is linearly proportional to the total number of elements in the collection n, then a counting sort will have a best-case and a worst-case time complexity of O(n), making it a very efficient sort in such a case.

Big Oh (and others in the Bachman-Landau family of notations) are just simplifications of the precise complexity of the function in any given case, used to illustrate the increasing value of the function as N grows large. In programming, Big Oh is usually used in the context of time complexity; for n values, a function f(n) will execute in a time on the order of g(n), and thus we say it has a Big Oh complexity of O(g(n)). However the mathematical construct of Big Oh isn't so limited. In this particular case, it is being used to refer to the general relationship between k and N as numbers.

Simply put, when k (the range of the values of an n-element collection) increases as n does on the order of O(n), then the counting sort will be efficient. This will be true if, say, the list contained all multiples of 4 between 1 and x (in which case k~=x, and n=x/4, meaning that k ~= 4n = O(n)). The condition k=O(n) would be false for, say, the set of all perfect squares from 1 to x2 (in which case k=x2 but n=x, so k = n2 = O(n2)). In that case, k increases on the square (O(n2)) when N increases linearly (O(n)), so the counting sort would execute in the more complex time (which would be O(n2)), which would perform worse than some other sort implementation that ran in Theta(nlogn).

| improve this answer | |
  • Not sure I get this.E.g. if x=256 then a list containing all multiples of 4 between 1 and x is [1,4,14,64,256].I guess k is the largest so k=256.Why is n=x/4?In this case it is n=256/4=64 but we only have 5 elements.I am trying to understand what you are saying here – user10326 Nov 1 '11 at 21:48
  • Uh, no. The list of all multiples of 4 between 1 and 256 is [4,8,12,16,20, ... 240,248,252,256]. This list will have n=64 elements and an inclusive range of k=253. This is on the order of k=4n-3, which in Big Oh terms is linear (O(n)). However, a list of the first N perfect squares would have a range k=n^2. As k increases on the square of n, the counting sort, which executes in time proportionate to the larger of k and n, will become less efficient. – KeithS Nov 9 '11 at 23:48

The complexity of a counting sort is O(max(k, n)), so if k = O(n) the sort runs in O(n) time.

| improve this answer | |
  • That is my question.What does k=O(n) mean in this context? – user10326 Nov 1 '11 at 18:11
  • It means that for k is no greater than some constant multiple of n. – kevin cline Nov 1 '11 at 23:22

At least as I interpret it, it's just saying that the range of the inputs and the number of inputs are kinda similar [Edit: least that be misunderstood, it's giving that as the condition under which the complexity is Theta(n), not saying that it's necessarily always true.]

Just for example, the usual estime is reasonable for a thousand or a million or a billion inputs of something like 32 or 64 bits each.

Ignoring, for the moment, the fact that you'd never actually finish, consider what would happen if you have a 500-digit (or 10,000 digit) number of 3-bit inputs. In such a case, the time taken to do each individual addition could start to become significant [Edit: I.e., would no longer be constant], so Theta(n) would no longer be accurate. In the usual case, we can ignore the time for the additions because it's a constant factor.

| improve this answer | |
  • Actually, it's saying that IF the range of inmputs and the number of inputs are similar, that a counting sort will be efficient. – KeithS Nov 1 '11 at 18:48

Your Answer

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

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