Services & Resources / Wolfram Forums
MathGroup Archive
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Efficiency of repeatedly appending to a List

  • To: mathgroup at
  • Subject: [mg71235] Re: Efficiency of repeatedly appending to a List
  • From: Jon Harrop <jon at>
  • Date: Sat, 11 Nov 2006 03:38:37 -0500 (EST)
  • References: <eisg8h$n5a$> <eius22$gkv$>

Jon Harrop wrote:
> Andrew Moylan wrote:
>> This caused me to wonder about the efficiency of appending items to
>> Lists in Mathematica in general. Is it an O(N) operation (i.e.,
>> something akin to a realloc in C)? Or does Mathematica employ some sort
>> of anticipatory memory allocation scheme to make adding new elements to
>> lists usually faster than O(N)?
> I think I tested this a while ago and found it to be amortised
> constant-time complexity.

I just tested it again:

l = {};
      First@Timing[Do[AppendTo[l, Random[]], {i, 100}]], {j, 100}] /. 
    Second -> 1]

and I was most certainly wrong, Append is O(n) as Daniel said.

Dr Jon D Harrop, Flying Frog Consultancy
Objective CAML for Scientists

  • Prev by Date: Too late to upgrade from 4.2 to 5.2....
  • Next by Date: Re: I could do with a list of geometric shape names can anyone help????
  • Previous by thread: Re: Efficiency of repeatedly appending to a List
  • Next by thread: CleanSlate