I am afraid this problem CANNOT be solved faster than O(n*log(n)) . If you can find a single repeated element in an array in O(n) then you can solve the element uniqueness problem. However this problem cannot be done in better than O(n * log(n) ). http://en.wikipedia.org/wiki/Element_uniqueness_problem
-Dhyanesh On 8/25/07, L7 <[EMAIL PROTECTED]> wrote: > > > > > Your solution really parses terms on what it means to be performing > > asymptotic analysis... you cannot say that this storage is constant in > > 32 bits, when it is not said that you are using 32 bit numbers. If you > > are speaking asymptotically at all, saying that something is O(n) or > > O(log(n)) or anything else then _by definition_ you are talking about > > infinity... > > > > Oh, and one more thing, O(1/n) is 0, so your reductio ad absurdum > fails. > > > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
