Re: [Caml-list] Simple question

[John Prevost <visigoth@cs.cmu.edu>]

>>>>> "em" == Eric Merritt <cyberlync@yahoo.com> writes:

    em> by this I assume that the '@' function is not as strait
    em> forward as I thought it would be? In what manner does it
    em> append to the list to make the time 0(n^2)? -just curious.

Actually, it's O(n) because it's straightforward and doesn't cause
side-effects.  The O(n^2) is when it is used n times.  Here's an
implementation that works similarly:

let rec append a b = match (a,b) with
  | [], _ -> b
  | h::t, _ -> h :: append t b

If you keep appending one element onto the end of a list, you can see
that append has to run down the entire first list each time to build a
new list with your new value at the end.  If you append one item at
the beginning each time, it behaves substatntially like :: does.

So (@) is O(n) with n being the size of the first argument.

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