(a) Explain why counting sort may not be able to sort the integers in O(n) time.

(b) Explain why radix sort may not be able to sort the integers in O(n) time.

(c) Given (a) and (b), explain why we can typically regard counting sort and radix sort as Θ(n) sorts when the keys are integers.

(d) Compare the asymptotic running time of radix sort and counting sort when the conditions for both to be linear hold.

Answer rating: 100% (QA)

a Counting Sort and On Time Counting Sort is often regarded as an On sorting algorithm but this is contingent on certain conditions It can sort intege... View the full answer