what is time complexity of append (vector / list)?

Question

https://www.programmingr.com/fast-r-append-list/

I don't find the time complexity of the appending operation on a vector or a list.

Is this documented anywhere?

Suppose that I have n elements, that I have to append one by one. Is there a data structure that has a time complexity of n to append the n elements?

Answer 1

Here is a function to test the running times of three different ways of assigning a value to a vector.
The first two extend the vector by appending the new element to its end. The last one allocates space by creating a vector with n elements and then populates the vector with the new elements.
Times are measured with package microbenchmark and medians are plotted with ggplot2 graphics.

Atomic vector timings

fun <- function(N = 1:10, times = 100){
  if(!require(microbenchmark)){
    stop("Package 'microbenchmark' is not installed")
  }
  out <- lapply(2^N, function(n){
    mb <- microbenchmark(
      c = {
        x <- NULL
        for(i in seq_len(n)) x <- c(x, i)
      },
      append = {
        x <- NULL
        for(i in seq_len(n)) x <- append(x, i)
      },
      allocate = {
        x <- numeric(n)
        for(i in seq_len(n)) x[i] <- i
      },
      times = times
    )
    mb$n <- n
    aggregate(time ~ expr + n, mb, median)
  })
  out <- do.call(rbind, out)
  row.names(out) <- NULL
  out
}

library(ggplot2)

times <- fun(1:12)

ggplot(times, aes(n, time, color = expr)) +
  geom_line() +
  geom_point() +
  theme_bw()

---

list timings

This function is nearly identical to the function above, but creating and extending objects of class "list".

Surprisingly, now to extend the list by assigning new elements after the current last is faster than append.

funList <- function(N = 1:10, times = 100){
  if(!require(microbenchmark)){
    stop("Package 'microbenchmark' is not installed")
  }
  out <- lapply(2^N, function(n){
    mb <- microbenchmark(
      List = {
        x <- list()
        for(i in seq_len(n)) x[[i]] <- i
      },
      append = {
        x <- list()
        for(i in seq_len(n)) x <- append(x, i)
      },
      allocate = {
        x <- vector("list", n)
        for(i in seq_len(n)) x[[i]] <- i
      },
      times = times
    )
    mb$n <- n
    aggregate(time ~ expr + n, mb, median)
  })
  out <- do.call(rbind, out)
  row.names(out) <- NULL
  out
}

library(ggplot2)

times <- funList(1:12)

ggplot(times, aes(n, time, color = expr)) +
  geom_line() +
  geom_point() +
  theme_bw()