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.
