"Big Oh": Is my reasoning right?

Tanguy Andreani — Tue, 23 Jul 2019 19:04:49 +0000

Apologies for bad notation. Also, I'm not a native speaker.

I started reading this book:

I am currently reading the first chapter, which is about time complexity / asymptotic notation.

So I'm told that for an algorithm whose running time is described by the function 𝑇(𝑛) = 3𝑛³ + 2n² we have a worst-case complexity of O(𝑛³). Fine.

I'm told that I can easily prove that T(n) ≤ 5𝑛³. Fine. (I'm pretty confident in my highschool maths skills.)

Basically, I ended up with T(𝑛) ≤ 3.0...01𝑛³ for 𝑛 tends to +∞. A different value of 𝑐.

It might sound dumb that 3𝑛³ + something could be smaller than 3𝑛³ but I found this using limits.

My reasoning was that, after manipulating the inequality T(n) ≤ 𝑥𝑛³, one could end up with the following statement:

3 + 𝑛^-2 ≤ 𝑥

Now 𝑛 is just a positive integer constant. So let it be 1; smallest input. We end up with 𝑥 = 5. The value provided by the book.

But let's say that 𝑛 gets bigger and bigger; and eventually tends to +∞. Since 𝑛^-2 would then tend to 0, we have 𝑥 tends to 3.

So T(𝑛) ≤ 𝑥𝑛³ with 𝑥 a real number that tends to 3 from upper values but is not exactly 3. In fact, it wouldn't work with 3.

In GeoGebra

Click here if you can't see the video.

C is the point at which 𝑥𝑛³ gets bigger than T(𝑛).

My question

First of all, is my reasoning correct? Can I use this kind of reasoning when dealing with algorithms complexity? I'm pretty confident that it "holds" mathematically speaking but does it apply here?

I understand that it is not really important since we end up with the same O() but still, just curious.

Thank you.

Useful resources when studying Ruby's internals

Tanguy Andreani — Fri, 19 Jul 2019 12:10:21 +0000

I'm gonna list a few places I visit whenever I want to learn more about a specific part of Ruby.

Ruby MRI on Github

Link: https://github.com/ruby/ruby

The whole source code is mirrored there. Here you can learn how the language is implemented.

For example, if we want to learn about the Array class, we can look in array.c.

Let's say I'm interested in the Array#count method:

static VALUE
rb_ary_count(int argc, VALUE *argv, VALUE ary)
{
    long i, n = 0;

    if (rb_check_arity(argc, 0, 1) == 0) {
    VALUE v;

    if (!rb_block_given_p())
        return LONG2NUM(RARRAY_LEN(ary));

    for (i = 0; i < RARRAY_LEN(ary); i++) {
        v = RARRAY_AREF(ary, i);
        if (RTEST(rb_yield(v))) n++;
    }
    }
    else {
        VALUE obj = argv[0];

    if (rb_block_given_p()) {
        rb_warn("given block not used");
    }
    for (i = 0; i < RARRAY_LEN(ary); i++) {
        if (rb_equal(RARRAY_AREF(ary, i), obj)) n++;
    }
    }

    return LONG2NUM(n);
}

// ...

rb_define_method(rb_cArray, "count", rb_ary_count, -1);

The Ruby Spec Suite

Link: https://github.com/ruby/spec

Let's say I'm interested in the Array#count method:

describe "Array#count" do
  it "returns the number of elements" do
    [:a, :b, :c].count.should == 3
  end

  it "returns the number of elements that equal the argument" do
    [:a, :b, :b, :c].count(:b).should == 2
  end

  it "returns the number of element for which the block evaluates to true" do
    [:a, :b, :c].count { |s| s != :b }.should == 2
  end
end

Ruby-doc

Link: https://ruby-doc.org/

Documentation for pretty much every versions of Ruby MRI.

Here is the doc for Array#count

The Rubinius implementation

Link: https://github.com/rubinius/rubinius

Rubinius is basically Ruby implemented in Ruby. It's fun to compare with the original C implementation.

For example, here is the source code for Array#count:

def count(item = undefined)
  seq = 0
  if !undefined.equal?(item)
    each do
      element = Rubinius.single_block_arg
      seq += 1 if item == element
    end
  elsif block_given?
    each { |element| seq += 1 if yield(element) }
  else
    each { seq += 1 }
  end
  seq
end

Does it look like it match the Ruby spec?

JRuby, Ruby on the JVM

Link: https://github.com/jruby/jruby

I don't know Java but this project motivate me to learn about it.

Here is Array#count source code from JRuby's RubyArray.java:

@JRubyMethod(name = "count")
public IRubyObject count(ThreadContext context, Block block) {
    if (block.isGiven()) {
        int n = 0;
        for (int i = 0; i < realLength; i++) {
            if (block.yield(context, elt(i)).isTrue()) n++;
        }
        return RubyFixnum.newFixnum(context.runtime, n);
    } else {
        return RubyFixnum.newFixnum(context.runtime, realLength);
    }
}

@JRubyMethod(name = "count")
public IRubyObject count(ThreadContext context, IRubyObject obj, Block block) {
    if (block.isGiven()) context.runtime.getWarnings().warn(ID.BLOCK_UNUSED, "given block not used");

    int n = 0;
    for (int i = 0; i < realLength; i++) {
        if (equalInternal(context, elt(i), obj)) n++;
    }
    return RubyFixnum.newFixnum(context.runtime, n);
}

Those are methods of the Java class RubyArray.

Bonus, the Mailing Lists Archive for Ruby MRI

Link: http://blade.nagaokaut.ac.jp/

Summary:

Regarding gems and their documentation (offtopic but cool to have anyway):

Anything to add to the list?

DEV Community: Tanguy Andreani