This is also my suspicion. BTW, thanks to all for an interesting discussion. I'm not completely sure that the problem can be reduced to an element uniqueness problem, but I suspect there is a relation. Alas, I'm not an expert in complexity...
On Aug 25, 7:43 pm, "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 [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 -~----------~----~----~----~------~----~------~--~---
