Question

Consider this way to sort. You are given N integers in an array (the data source). You are told that the integer values will be in the range 0 to K, that there are no duplicate values, and that N < K. To sort them smallest to largest, you build another array of K boolean values that are initially all false. You go through the data source array and for each element you use the integer value stored as a subscript into the boolean array and mark that slot as true. Finally, to get the sorted sequence, you go through the boolean array starting at subscript 0 and print the subscript for every element that contains true. Which of the following expressions is the best description of the worst case time complexity for this sort?

A. O(N)
B. O(N²)
C. O(N log N)
D. O(N*K)
E. O(N²*K)
F. O(N log N*K)
G. O(N+K)
H. O(N²+K)
I. O(N log N+K)

Answer 1

The worst case time complexity for this sort is O(NK), where N is the number of elements in the data source array and K is the range of integer values.

Step-by-step explanation:

The worst case time complexity for this sort can be described as O(NK). Here's a step-by-step explanation:

1. Create an array of K boolean values, initially all set to false.
2. Iterate through the data source array with N elements.
3. For each element, use its integer value as a subscript into the boolean array and mark that slot as true.
4. Finally, iterate through the boolean array and print the subscript for every element that contains true.

In the worst case scenario, where N is the number of elements in the data source array and K is the range of integer values, all N elements will have different values and need to be marked as true in the boolean array. Hence, the time complexity is O(NK). This is because for each element, the average time complexity for marking the slot as true is O(K).