[R] complexity of operations in R

[R. Michael Weylandt]

> 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:

http://www.joelonsoftware.com/articles/fog0000000319.html

Michael