The mathematical explanation for the nlogn lower bound assumes the number of different permutations possible to be n! .In the dutch flag problem the number of possible permutations are much lower.....As a matter of fact there is only one type of comparison.The one compared with a zero. Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com
On Mon, Jan 23, 2012 at 12:56 PM, 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.
