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@haskell.org http://www.haskell.org/mailman/listinfo/haskell