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
- Follow-Ups:
- Re: complexity of AppendTo
- From: Daniel Lichtblau <danl@wolfram.com>
- Re: complexity of AppendTo