Browse thread
[Caml-list] function
[
Home
]
[ Index:
by date
|
by threads
]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: | 2002-12-05 (23:01) |
From: | Oleg <oleg_inconnu@m...> |
Subject: | Re: [Caml-list] function |
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