What is the order of complexity of += Array in Ruby?

Question

Say I have an array a with length n, and I wish to add another another array b with length m. Namely

a+=b

What is the order of complexity for such operation? I know that in PERL, it has a buffer, so if m isn't large, it is ~ o(m). Let us us take two cases:
1. m << n
2. m ~ n
Thanks.

Why do you make the question complicated? You could have asked the complexity of `Array#+`. — sawa, Oct 22 '13 at 11:35

score 1 · Answer 1 · edited May 23 '17 at 12:22

Probably I won't give You the full answer, but for starters check implementation of Array#+ in C:

VALUE rb_ary_plus(VALUE x, VALUE y)
{
    VALUE z;
    long len;

    y = to_ary(y);
    len = RARRAY_LEN(x) + RARRAY_LEN(y);
    z = rb_ary_new2(len);
    MEMCPY(RARRAY_PTR(z), RARRAY_PTR(x), VALUE, RARRAY_LEN(x));
    MEMCPY(RARRAY_PTR(z) + RARRAY_LEN(x), RARRAY_PTR(y), VALUE, RARRAY_LEN(y));
    ARY_SET_LEN(z, len);
    return z;
}

As You can see it defines new instance, copies over array X, then it copies array Y. MEMCPY is a macro, that should wrap memcpy(). As this answer suggests C's memcpy is O(N) - How do realloc and memcpy work?

So in our case it will be ~O(N+M). I suggest You to further examine Ruby source code. It's quite probable that in case of += it performs only single memcpy. Also we have different implementations of Ruby.

What is the order of complexity of += Array in Ruby?

1 Answers1