from array update algorithm to nice Haskell code

[Wolfgang Jeltsch]

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