@Don : if i am not wrong ... American flag problem is closely related to radix sort not dutch flag.
On Mon, Jan 23, 2012 at 11:16 PM, Don <[email protected]> wrote: > 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. > > -- 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.
