-4

Suppose I want to subsequently add elements to a void vector in R. For instance:

a=numeric()
for (j in 1:n) a[j]=j

What is the complexity of this operation? n^2? In other words, does R in each iteration reallocate the vector a?

(Actually in my case the number of iterations is calculated within the loop, so it is impossible to predict the final length of the vector and allocate the vector before the loop.)

Viktor
  • 472
  • 5
  • 14
  • As far as I see, using `append` will surely have n^2 complexity. – Viktor Feb 10 '17 at 17:04
  • Jaap, please return "R" to the title of the question. The question is R-specific!! – Viktor Feb 10 '17 at 17:10
  • 1
    No, the question is tagged R. So, that's enough. See [this Q&A](http://meta.stackexchange.com/questions/19190/should-questions-include-tags-in-their-titles) for reference. – Jaap Feb 10 '17 at 17:15
  • Also: Please read the info about [how to ask a good question](http://stackoverflow.com/help/how-to-ask) and how to give a [reproducible example](http://stackoverflow.com/questions/5963269/how-to-make-a-great-r-reproducible-example/5963610). This will make it much easier for others to help you. – Jaap Feb 10 '17 at 17:16
  • In the instance that you don't know the final length of the vector, you can always over-allocate the vector and then remove unused elements at the end. For example, if you expect it to be 500 elements, give it double the expected length. `numeric(100L)`. Another method is to intermittently double the size if it gets filled up. – lmo Feb 10 '17 at 18:40

1 Answers1

0

The vector is reallocated in each iteration. So the complexity is n^2.

Viktor
  • 472
  • 5
  • 14