Re: [Caml-list] function

[Xavier Leroy <xavier.leroy@inria.fr>]

> If the given list has L elements, each with S items, then flatten should 
> O((L*S)*L) = O(S*L^2) time, since you have to keep on churning through
> every single element in the ever-expanding l at every recursive flatten 
> call.  That's too bad.
> Here's an experiment I tried:
> [...]
> I guess it looks linear because of the small input size.

It's always a good idea to do experimental measurements to confirm a
complexity analysis, just to make sure you haven't goofed.  But when
the measurements disagree with the analysis, you're supposed to go
back to the analysis and find the flaw in it, not discard the
experiment :-)

More seriously: l1 @ l2 takes time O(length(l1)); the length of l2
doesn't matter since l2 isn't copied.  This gives List.flatten a
complexity of O(S*L) in your example (list of length L, each list
element being of length S).  This is optimal for immutable,
singly-linked lists.

- Xavier Leroy
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners