# Auxiliary space complexity of map vs map!

I'm curious about the difference in space complexity between `map` and `map!` in ruby.

If I have the methods:

``````def mult_by_two(arr)
arr.map {|i| i * 2 }
end

def mult_by_two!(arr)
arr.map! {|i| i * 2 }
end
``````

While there's no explicit assignment in the first method, it's implicitly collecting the result of the `map` somewhere and is not operating in-place like the second method.

Would it be correct to say that the first has O(n) auxiliary space complexity while the second is O(1)? How should I represent them when looking at the auxiliary space complexity of a method?

The answer is hidden in the source of the page Ruby-doc: Core Array

If one goes to Ruby-doc: Core Array#map or Ruby-doc: Core Array#map! and mouses over the block, they will see

Clicking the 'click to toggle source' then gives us the C source code that implements the method in the interpreter.

For `map` the code is:

``````collect = rb_ary_new2(RARRAY_LEN(ary));
for (i = 0; i < RARRAY_LEN(ary); i++) {
rb_ary_push(collect, rb_yield(RARRAY_AREF(ary, i)));
}
``````

For `map!` the code is:

``````rb_ary_modify(ary);
for (i = 0; i < RARRAY_LEN(ary); i++) {
rb_ary_store(ary, i, rb_yield(RARRAY_AREF(ary, i)));
}
``````

One can clearly then see that `map` allocates a new array of the length of the original array and pushes the values that are used into this array while `map!` stores the value in the initial array.

Thus, you are correct - `map` uses O(n) auxiliary space while `map!` uses O(1) (none at all).

array.map: "Invokes the given block once for each element of self. Creates a new array containing the values returned by the block.".

array.map!: "Invokes the given block once for each element of self, replacing the element with the value returned by the block.".

The first allocates a new array of the same size, the second does not. The "space complexity" of both are exactly the same: O(1). The "auxiliary space usage" of map is O(N), for map! is O(1).

The main reason to use map! is to avoid the extra allocation which eventually has to be garbage collected.