[R] complexity of operations in R

R. Michael Weylandt michael.weylandt at gmail.com
Thu Jul 19 22:21:39 CEST 2012

> On Thu, Jul 19, 2012 at 3:00 PM, Jan van der Laan <rhelp at eoos.dds.nl> wrote:
> When the length of the end result is not known, doubling the length of the
> list is also much faster than increasing the size of the list with single
> items.
> [snip]
> What causes these differences? I can imagine that the time needed for memory
> allocations play a role: multiple small allocations will be smaller than one
> large allocation. But that doesn't explain the quadratic growth in time. I
> would expect that to be linear. When doing v[[i]] <- i the list isn't
> copied, right?

I wouldn't be so sure: see the description of the algorithmic
properties of malloc() here:



More information about the R-help mailing list