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

Re: [Caml-list] Applications written in O'Caml
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: -- (:) From: Remi VANICAT Subject: Re: [Caml-list] Simple question
```Eric Merritt <cyberlync@yahoo.com> writes:

> > erg, apply_fun_list become tail recursive, but it's
> > in O(n^2) (when
> > the first version is in O(n)), and as @ is not tail
> > recursive, this
> > doesn't resolve the problem of Usage of the
> > stack....
> >
> > better stick to the non tail recursive version that
> > to do this.
>
> by this I assume that the '@' function is not as
> strait forward as I thought it would be? In what
> manner does it append to the list to make the time
> 0(n^2)? -just curious.

so let's look at :

let rec apply_fun_list x f_list accum =
match f_list with
h::t ->
apply_fun_list x t (accum@(h x))
| [] ->
accum;;

so the line "apply_fun_list x t (accum@(h x))" is done O(n) time (one
time for each element in f_list), and "(accum@(h x))" take time O(n),
so the time taken by this algorithm is O(n)*O(n)=O(n^2).

--
Rémi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat
-------------------
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

```