Question

1. what conditions does counting sort run in a linear line

2. which has the best running time. assume we sort n #s in range 0 to n^2 using radix sort(counting sort to sort each digit)

- all n numbers in decimal form(radix-10)

- all n numbers are represented in radix-n

Answer 1

1. Time complexity of counting sort is O(n). Count sort runs on a condition that it will initially generates a new array based on the maximum element. Then by iterating through the entire array, it will count how many times each element occurs using for loop. Based on this condition counting sort run in a linear line.

2. Radix sort has a best running time when it comes to run in the range of 0 to n² .

Radix sort is a specific type of sorting technique which starts with the top n-bit or n-digits and may sort those buckets using a radix sort etc, until every entry is sorted.

Counting sort is like using radix sort except you are using the whole value. Instead of recording each object, it has a bucket for each object and it just counts the number of occurrences. This works well when you have a limited number of possible keys and you have many duplicates.