set representation question

[Stefan Karrmann]

Dear Nicholas,

Nicholas Nethercote (Wed, Nov 12, 2003 at 11:32:54AM +0000):
> On Wed, 12 Nov 2003, Tom Pledger wrote:
> 
> > Hal Daume III writes:
> >  :
> >  | *all* i care about is being able to quickly calculate the size of
> >  | the intersection of two sets.  these sets are, in general, very
> >  | sparse, which means that the intersections tend to be small.
> >  |
> >  | for example, i might have two sets reprsented by the arrays:
> >  |
> >  |  {0,1,10,346,398,1039,3289,3853,9811,89231,50913}
> >  |  {0,3,98,183,398,1038,5319,7642,9811,13893,93123}
> >  |
> >  | and all i need to be able to do is respond with "3" very very
> >  | quickly.  using sorted arrays, this takes O(n+m) time (where n and
> >  | m are the sizes of the arrays).
> >
> > The total time (including the up front time for building the data
> > structure) can't go below O(n+m), because if it did, you'd be
> > neglecting to look at some of the elements at all.
> 
> Isn't it O(min(m,n))?  You don't have to look at all elements for the
> intersection.  Eg:
> 
>   {0,1,10}
>   {0,3,98,183,398,1038,5319,7642,9811,13893,93123}

O(f) describes the worst case of the algorithm. It is O((m,n)->m+n).
The average cost may be lower, but it depends on the distribution of the
data.

Sincerly,
-- 
Stefan Karrmann