Suppose an array A stores n integers, each of which is in {0, 1, 2, ..., 99}. Which of the following sorting algorithms can sort A in O(n) time in the worst case?
Question 16 options:









D) None of these options is correct
As for the comparison just look at the following table which shows the whole scenario of sorting algorithm time complexity of worstcase time complexity column for each sorting algorithm.
Algorithm  Data structure  Time complexity:Best  Time complexity:Average  Time complexity:Worst  Space complexity:Worst 

Quick sort  Array  O(n log(n))  O(n log(n))  O(n^{2})  O(n) 
Merge sort  Array  O(n log(n))  O(n log(n))  O(n log(n))  O(n) 
Insertion sort  Array  O(n)  O(n^{2})  O(n^{2})  O(1) 
Count Sort  Array  Ω(N + k)  Θ(N + k)  O(N + k)  O(k=n) 
Thanks
Get Answers For Free
Most questions answered within 1 hours.