Version française
Home     About     Download     Resources     Contact us    

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

Browse thread
[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 <xavier.leroy@i...>
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 
> 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 Archives:
Bug reports: FAQ:
Beginner's list: