Version française
Home     About     Download     Resources     Contact us    
Browse thread
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: John Prevost <visigoth@c...>
Subject: Re: [Caml-list] Simple question
>>>>> "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