from array update algorithm to nice Haskell code

[Daan Leijen]

Hi Wolfgang,

>> I think that you are mixing up worst case bounds O(..) with some specific
>> case. I guess that you mean by "O(1) elements" a known and constant number
>> of elements.
>
> I mean a constant maximum number of elements.  An example would be that the
> set b is guaranteed to have not more than one element.

Ah, I think I have the gist of your message now. For DData.Set, the
worst case bound for intersect is O(n+m), however, for your particular
case, it will behave as you want. i.e. for an intersection where one
of the sets is empty, it will run in constant time; for an intersection
where one of the sets has one element, it will take at most O(log n) time
(where n is the number of elements in the other set). This is again a
worst case bound: if n is zero (the empty set), it will be a constant
time operation. Even stronger, if you ask for the intersection of two large
sets that have no common elements, the operation will take (log n + log m) time.

Still, in the worst case, where both trees have about the same size and the
same kind of elements, the algorithm will degenerate to O(n+m). (btw. this is not
the case when you would simply iterate over one set and test membership of
the other (= O(m*log n)))

I am not entirely sure if this also holds for Data.Set, but I guess it is
the same. A small issue is that it *does* pay off to swap the arguments if
their size differs (just as in your list example), and I don't know
if Data.Set does that -- you should look in the CVS sources to find out.

If you think that application to the sets with single values happens often,
maybe I should add some special-case code to make this more (absolutely) efficient.


All the best,
  Daan.



>> However, in the worst case, this will degenerate to some "m" number of
>> elements, and your function would take O(m*log n) time, i.e. much worse than
>> O(n+m).
>
> I don't understand this.  If m doesn't depend on any input values but is
> really constant then O(m * log n) = O(log n)—regardless of how large m is.
>
> Well, the specification of O(n + m) time does only say that the time is less
> than c * (n + m) of some constant c which is no contradiction to an O(log n)
> time.  But it leaves the possibility open that the calculation really needs
> linear time.
>
>> All the best,
>>   Daan.
>
>> [...]
>
> Wolfgang
>
> [1] Schöning, Theoretische Informatik – kurzgefasst, Spektrum Akademischer
> Verlag
>
> _______________________________________________
> Haskell mailing list
> Haskell at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell
>
>