Re: Efficiency of repeatedly appending to a List

*To*: mathgroup at smc.vnet.net*Subject*: [mg71132] Re: [mg71091] Efficiency of repeatedly appending to a List*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Thu, 9 Nov 2006 03:37:41 -0500 (EST)*References*: <200611081114.GAA22363@smc.vnet.net>

Andrew Moylan wrote: > 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 Append and Prepend are O(n) operations. The mechanism underlying Sow involves the sort of anticipatory allocation scheme you may have in mind; it is on average O(1). But unlike ordinary Mathematica expressions, Sow builds something it in effect "knows" is only going to grow (until it is Reap'd), and only in one direction. Of course if you want fast(er than O(n)) searching AND insertion, you need a different data structure anyway; perhaps a tree of some, er, sort. Daniel Lichtblau Wolfram Research

**References**:**Efficiency of repeatedly appending to a List***From:*"Andrew Moylan" <andrew.j.moylan@gmail.com>