From: Matt Armstrong <matt@...>
Date: 2002-03-21T08:44:07+09:00
Subject: Re: Why is Ruby so slow? - Solution

Ron Jeffries <ronjeffries@REMOVEacm.org> writes:

> 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.

You mean O(1)?  Linear array lookups are O(N).


-- 
matt