@ATUL..still we are not comparing elements among themselves....The ordering of elements is already known to us Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com
On Tue, Jan 24, 2012 at 10:19 AM, atul anand <[email protected]>wrote: > @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. > -- 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.
