Re: [Caml-list] Simple question

[Remi VANICAT <vanicat@labri.u-bordeaux.fr>]

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