MathGroup Archive 2002

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

Search the Archive

complexity of AppendTo

  • To: mathgroup at smc.vnet.net
  • Subject: [mg32943] complexity of AppendTo
  • From: Gerhard Wesp <gwesp at cosy.sbg.ac.at>
  • Date: Thu, 21 Feb 2002 02:06:54 -0500 (EST)
  • Organization: Department of Computer Science, Salzburg University
  • Reply-to: gwesp at cosy.sbg.ac.at
  • Sender: owner-wri-mathgroup at wolfram.com

% math
Mathematica 4.1 for Linux
Copyright 1988-2000 Wolfram Research, Inc.
 -- Motif graphics initialized -- 

In[1]:= Table[ l = Table[ {} , { n } ] ; 
  Timing[ AppendTo[ l , {} ] ][[1]] , { n , 10^6 , 4*10^6 , 10^6 } ]

Out[1]= {0.5 Second, 1. Second, 1.49 Second, 2. Second}

In[2]:= % / %[[1]]

Out[2]= {1., 2., 2.98, 4.}


obviously, AppendTo takes O(n) time.  why is this?  if List[] is
implemented as a linked list, the complexity should be constant.  and
even for vectors, it is trivial to implement amortized constant time
append.

(for c++ programmers: compare this to std::list<> and std::vector<>, or
std::deque<>)

regards,
-gerhard
-- 
| voice: +43 (0)676 6253725  ***  web: http://www.cosy.sbg.ac.at/~gwesp
|
| Passts auf, seid's vuasichdig, und lossds eich nix gfoin!
|  -- Dr. Kurt Ostbahn


  • Prev by Date: Re: Fourier coefficients
  • Next by Date: Re: Fourier coefficients
  • Previous by thread: Re: function defining including solve command
  • Next by thread: Re: complexity of AppendTo