I am not sure that this is exactly the element uniqueness problem, however -- does it matter in this problem statement that you are told that there is a repetition, and that the goal is to find it? I am not sure if that changes the problem or not...
I agree with you though, that there is no solution. I also think that enforcing the Read-Only memory constraint and Constant Space kills the O(nlog(n)) low bound, as there is no way to sort... On Aug 25, 11:43 am, "Dhyanesh (ધયાનેશ)" <[EMAIL PROTECTED]> wrote: > 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 algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
