1

Counting sort worst, best and average time complexity is O(n+k), where n is number of elements to sort. What is k exactly? I see different definitions: maximum element, difference between max element and min element, and so on.

  1. Given array arr1 [1, 3, 5, 9, 12, 7 ] and arr2 [1,2,3,2,1,2,4,1,3,2] what is k for arr1 and arr2?
  2. Is it true that it is stupid to sort arr1 with counting sort because n < k (element values are from a range which is wider than number of elements to sort?
Code Complete
  • 3,146
  • 1
  • 15
  • 38
  • 1
    I don't think that there is an "and so on". –  Aug 03 '17 at 16:13
  • 1
    You presumably mean "when `n < k`" rather than "because `n > k`". –  Aug 03 '17 at 16:17
  • It depends on how you coded it. You may want to look up the algorithm or review the basics of time complexity, because that should allow you to very easily figure this out yourself. This is essentially a duplicate of [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm). – Bernhard Barker Aug 03 '17 at 16:22

3 Answers3

3

k is maximum possible value in array, assume you have array of length 5 which each number is an integer between 0 and 9, in this example k equals to 9

Farnabaz
  • 4,030
  • 1
  • 22
  • 42
  • Thank you for sharing knowledge! Did I get right your answer: for array of 3 elements [3, 20, 57] k = 57 ("k is maximum possible value in array")? Right? – Code Complete Aug 03 '17 at 16:41
2

k is the range of the keys, i.e. the number of array slots it takes to cover all possible values. Thus in case of numbers, Max-Min+1. Of course this assumes that you don't waste space by assigning Min the first slot and Max the last.

It is appropriate to use counting sort when k does not exceed a small multiple of n, let n.k, as in this case, n.k can beat n.log n.

  • Thanks a lot! May I ask "number of array slots it takes to cover all possible values. Thus in case of numbers, Max-Min+1" means for array of 3 elements [3, 20, 57] k = 3 (we have 3 possible values, so just 3 "array slots") or k = 55 (57 - 3 + 1)? P.S. I understand that k >> n, so I shall prefer radix sort, not use counting sort... – Code Complete Aug 03 '17 at 16:37
  • @CodeComplete: you can as well have `k < n`. –  Aug 03 '17 at 16:55
0

First an array of k counts is zeroed. Then the n elements in the array are read, and the elements of the k counts are incremented depending on the values of the n elements. On the output pass of a counting sort, the array of k counts is read, and array of n elements is written. So there are k writes (to zero the counts), n reads, then k reads and n writes for a total of 2n + 2k operations, but big O ignores the constant 2, so the time complexity is O(n + k).

rcgldr
  • 27,407
  • 3
  • 36
  • 61
  • Do I get right, that if we say that counting sort time complexity is O(n+k), then n is number of all elements to sort and k is number of DISTINCT elements? For example for array [ 3, 5, 7, 5, 1, 5] n = 6 and k = 4 ? – Code Complete Aug 04 '17 at 20:40
  • @CodeComplete - Normally k is the range of numbers, maximum value + 1 - minimum value. The size of the counting array is then k. For [3 5 7 5 1 5], k would be 7 (max value of 7 + 1 - min value of 1). – rcgldr Aug 04 '17 at 23:04