On Thursday 05 December 2002 03:24 pm, Issac Trotts wrote:
>   List.concat (List.map to_list2 strs);;

    ^^^^^^^^^

> > 2)  What is the complexity of your function f ?
>
> The new ones have linear time complexity w.r.t. the number of
> characters.  The old one has quadratic time complexity.

Issac

I haven't analyzed your whole functions, but List.flatten'ing alone is 
O(S*L^2), so while it may be linear WRT the number of characters in one 
string, it's not necessarily linear WRT the total number of characters. See 
my version of f for O(L*S) time.

Cheers
Oleg
-------------------
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