ericunfuk wrote: > Arunachalam wrote: > > Search the groups, this problem is already solved in O(n) time in the > > groups. > > > > regards > > Arunachalam. > > I solved it with n/2 case, I dont see how to do that with n/t, t > arbitrary.
I think this is equivalent to sorting. Consider the special case where you ask if any element occurs twice. You can do this in O(n) time with a radix sort. If your only operation is comparisons then each element will have to be compared to the element with the nearest value (otherwise you can't be sure they aren't equal). If I could compare all elements to their nearest (in value) neighbor in O(n) time, then I could also sort in O(n) time. Since I can't comparison-sort in O(n) time, I can't use comparison tests to find duplicates in O(n) time. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
