from array update algorithm to nice Haskell code
Daan Leijen
daanleijen at xs4all.nl
Fri Jan 9 23:45:36 EST 2004
> Now assume that I have a set a with O(n) elements and a set b with O(1)
> elements.
You can't have "O(1) elements" ... (A bound like O(..) talks about
the worst case time/space of an operation.)
> a `minusSet` b would take O(n) time and so would a `intersect` b.
> If I'd use
> foldr (flip delFromSet) a (setToList b)
> and
> [x | x <- setToList b, x `elementOf` a]
> instead of a `minusSet` b and a `intersect` b, I would get away with O(log n)
> time.
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.
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).
All the best,
Daan.
>
> Is this true?
>
> Wolfgang
>
> _______________________________________________
> Haskell mailing list
> Haskell at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell
>
More information about the Haskell
mailing list