From: Ron Jeffries <ronjeffries@...>
Date: 2002-03-21T05:43:00+09:00
Subject: Re: Why is Ruby so slow? - Solution

On Wed, 20 Mar 2002 14:21:23 -0500, Ron Jeffries <ronjeffries@REMOVEacm.org>
wrote:

>>> I'm curious. How do you do this operation in O(N+M)?
>>
>>Once making a hash whose keys are the minuend's elements, and
>>remove the subtrahend's elements from it.  At last, for all the
>>minuend's elements, add it to the result array if it is
>>contained in the hash.  Oops, sorry, it was O(2*N+M).
>
>Assumes hash lookup is O(N) which it might not be. Close enough for me tho.
>Thanks!

Never mind. It's O(N) up until your virtual memory spills, which is long enough
for most porpoises.

Ronald E Jeffries
http://www.XProgramming.com
http://www.objectmentor.com
I'm giving the best advice I have. You get to decide whether it's true for you.