Efficiency of repeatedly appending to a List

*To*: mathgroup at smc.vnet.net*Subject*: [mg71091] Efficiency of repeatedly appending to a List*From*: "Andrew Moylan" <andrew.j.moylan at gmail.com>*Date*: Wed, 8 Nov 2006 06:07:11 -0500 (EST)

Hi all, Recently I asked about efficient ways to insert items into a sorted List such that the new list was also sorted [1]. I received suggestions to linearly search through the list and find the right place to insert the new time (search time = O(N), where N is the size of the list), and also suggestions to use a faster binary search to locate the right place to insert the new time (search time = O(Log[N])). 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)? Cheers, Andrew [1] http://groups-beta.google.com/group/comp.soft-sys.math.mathematica/browse_thread/thread/0c329c83dec5a1b1

**Follow-Ups**:**Re: Efficiency of repeatedly appending to a List***From:*János <janos.lobb@yale.edu>