CODEWITHSUNDEEP
rubytime-complexity
Mahesh Mesta
Mahesh Mesta

Reputation: 783

Time Complexity for map and compact methods in Ruby

I want to know how to calculate the time complexity of the ruby map and compact method. In any case what would be the actual big O notations for them

Upvotes: 1

Views: 977

Answers (1)

TedTran2019
TedTran2019

Reputation: 1037

O(N), with no other alternatives.

All map does is apply your block of code onto every element of the array, pushing each result into a new array, then returning the new array.

All compact does is go through every element of the array, putting non-nil elements into a new array then returning said new array.

Source code for Array #each, #map, #compact, and #compact!

rb_ary_each(VALUE ary)
{
    long i;
    ary_verify(ary);
    RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length);
    for (i=0; i<RARRAY_LEN(ary); i++) {
    rb_yield(RARRAY_AREF(ary, i));
    }
}

rb_ary_collect(VALUE ary)
{
    long i;
    VALUE collect;

    RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length);
    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)));
    }
    return collect;
}

rb_ary_compact(VALUE ary)
{
    ary = rb_ary_dup(ary);
    rb_ary_compact_bang(ary);
    return ary;
}

rb_ary_compact_bang(VALUE ary)
{
    VALUE *p, *t, *end;
    long n;

    rb_ary_modify(ary);
    p = t = (VALUE *)RARRAY_CONST_PTR_TRANSIENT(ary); /* WB: no new reference */
    end = p + RARRAY_LEN(ary);

    while (t < end) {
    if (NIL_P(*t)) t++;
    else *p++ = *t++;
    }
    n = p - RARRAY_CONST_PTR_TRANSIENT(ary);
    if (RARRAY_LEN(ary) == n) {
    return Qnil;
    }
    ary_resize_smaller(ary, n);

    return ary;
}

Basically what Aleksei Matiushkin said.

Upvotes: 3

Related Questions