The Dutch Flag problem falls into the same category as radix sort, which is not a comparison-based sorting algorithm. Don
On Jan 23, 1:26 am, atul anand <[email protected]> wrote: > Hi all, > > as we all know that any sorting algorithm based on comparison model has > lower bound of nlogn i.e Omega(nlogn). > which can be proved mathematically. > > but as we all know dutch flag problem can sort 3 distinct elements (used > repeatedly) in O(n) time.It is also based on comparison model but can sort > in O(n) time. > so how can we justify lower bound of sorting based on comparison model , > because dutch flag problem kinda violates that. > > please help me understanding the difference..... > > Thanks -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
