insert method in Ruby Array order of complexity

Question

What is the expected order of magnitude of inserting in Array, in Ruby, when n is the Array size?
Thanks

Answer 1

TL;DR Appending (a special form of inserting) an item to the end of an array is usually done in O(1) time.

Let's walk through the (MRI) ruby source code to see why this is the case. We start at this line of ruby code:

a = [1,2]

Ruby prepares an array object, and then initialises it in this C function. The arguments are checked for validity and then it sets the capacity of the new array to the estimated length of the array with:

ary_resize_capa(ary, len);

The capacity of an array is the number of elements the array can possibly hold within the chunk of memory it has allocated from the operation system. The length of an array (the number of elements the array actually holds) is always smaller or equal to the capacity. By setting the capacity of the array, ruby ensures that enough memory is allocated to hold len number of items in the array.

Now, let's add an element to the end of the array:

a << 3

The source of the << function looks like this:

VALUE
rb_ary_push(VALUE ary, VALUE item)
{
    long idx = RARRAY_LEN(ary);
    VALUE target_ary = ary_ensure_room_for_push(ary, 1);
    RARRAY_PTR_USE(ary, ptr, {
    RB_OBJ_WRITE(target_ary, &ptr[idx], item);
    });
    ARY_SET_LEN(ary, idx + 1);
    return ary;
}

This code doesn't look too scary. It finds that the index (idx) of the new element is the length of the array, ensures that the array has enough memory to hold the new element (ary_ensure_room_for_push), writes the new element into the array, and increases the array length.

When the capacity of the array is larger than its length, no further memory needs to be allocated in ary_ensure_room_for_push and the operation can finish within O(1) time.

When the capacity of the array equals its length (the amount of memory in the array can exactly hold the number of elements it has), ary_ensure_room_for_push needs to increase the capacity so that one more element can be held by the array. Let's see how this is done:

static VALUE
ary_ensure_room_for_push(VALUE ary, long add_len)
{
    long old_len = RARRAY_LEN(ary);
    long new_len = old_len + add_len;
    long capa;

    // ...

    rb_ary_modify(ary);
    capa = ARY_CAPA(ary);
    if (new_len > capa) {
        ary_double_capa(ary, new_len);
    }

    return ary;
}

We see that ary_ensure_room_for_push doubles the arrays capacity if the requested length exceeds the current capacity (under the hood ary_double_capa uses the ary_resize_capa method we've seen during the array initialization). This code requests a new (bigger) chunk of memory from the operation system and copies all array elements into this new memory. We can't exactly say which complexity the copy operation has (without looking too much at operation system internals), but let's assume it's O(n) in the worst case.

This results in a O(1) time for adding an element to an array when the new element fits into the arrays capacity and O(n) if the capacity is exceeded.

FYI: Doubling the capacity (instead of increasing it exactly by the requested length) is a neat trick to optimize the case of adding elements to an array multiple times. With this trick we have an O(1) time for the append operation most of the time. Only for every log(n)'th append operation the capacity needs to be increased, resulting in a O(n) runtime.