This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

[Caml-list] function
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2002-12-07 (10:28) From: Xavier Leroy Subject: Re: [Caml-list] function
```> 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
> 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,