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
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: 2002-04-15 (13:05)
From: John Prevost <visigoth@c...>
Subject: Re: [Caml-list] Simple question
>>>>> "em" == Eric Merritt <> 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.

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