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-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 ( 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.


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.

To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: