cormen

Question

counting sort assumes that each of the n input is an integer in the range 0 to k, for some integer k.

please explain when k=O(n), the sort run in O(n) time.

Answer 1

Suppose we have n keys that are non-negative integers such that the biggest key, k, is not much bigger than the number of keys, i.e. k = O(n).

Take three arrays, A, B, and C. A is the input array with n keys. B is the sorted output array, also of length n. C will be our counting array of length k + 1.

then Apply counting sort algorithm

Since k = O(n), each for loop in algorithm does about n things, so counting sort has running time O(n).

For more info refer here http://www.cs.otago.ac.nz/cosc242/pdf/lecture9.pdf

http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap09.htm

Comments

thnxs :)

Answer 2

Counting sort Time complexity T(n)=O(n + k) , where n=number of elements in the array.
                                                                                       k=range of the number.
                                                                          Hence ,when  k=O(n)  running time becomes O(n).