First check this link http://users.monash.edu/~lloyd/tildeAlgDS/Sort/Flag/
The DNF algorithm is a way to implement 2 way or 3 way or k-way partition quicksort, the question is that if there are K number of distinct elements in total N elements then what is complexity for sorting them?
Lets assume that number of distinct elements is 3 in N total elements, for simplicity assume they are 0 , 1 and 2 , so list would look like this after sorting is completed.
00000....11111.....22222222
The DNF shows 3 way quicksort because there are 3 distinct integers in the list.
So question suggest that what is the complexity for sorting operation on list if we were to perform K way quicksort on the list of the N integers having K distinct integers
Consider you have N objects and K colours and assuming that only constant of proportionality in time changes the complexity will be O(NK)
Key is in "Notes" section
The DNF algorithm can be extended to four, or even more colours but it grows more and more complex to write, and the constant of proportionality in its running time increases.
Answer C .
Best Of Luck.
