Am Freitag, 9. Januar 2004 23:45 schrieb Daan Leijen: > > 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.)
Well, the O calculus isn't bound to resource analysis. According to [1] O is just something like O :: (Natural -> Natural) -> Set (Natural -> Natural) O f = {g | exists c. exists n0. forall n >= n0. g n <= c * f n}. Based on this definition, I mean that I have a quantity n (e.g. the size of a base set), and the size of the set a is less than c * n for some constant c while the size of b is always less than a constant c'. > > 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. 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. > 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 [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell