rolandomantilla has asked for the wisdom of the Perl Monks concerning the following question:

This a general question and I need help again Perl Monks. I have a series of functions that I need to analyse in order to run them thru a perl program and I'm trying to make them into the Big O notation to see which one will be more efficient. The functions are 
2log(n)+n^2log(log(n))&
3loga(n)+2logb(n) #where a and b and the bases of the logarithm

[download]
What will the big O notations be?

Replies are listed 'Best First'.
Re: Big O notation
by roboticus (Chancellor) on Oct 14, 2011 at 16:34 UTC

    rolandomatilla:

    I've never studied big-O notation, but have heard a bit about it. Since it's intended to show how an algorithm scales, you generally only care about the dominant term (i.e., the term that grows biggest the fastest). The constant multiplier is ignored.

    So the first one turns into O(log(n)), and the second one terms into O(logx(n)) where x is the smaller of a or b. (Remember log10(1024) is roughly 3 while log2(1024) is 10, so log2(n) grows faster.)

    Anyway, that's my uneducated take on it. I'm sure others will pipe up and let us know what I got wrong, and add refinement where needed.

    Update: I forgot to mention that the algorithm that scales better can be a worse performer until your data set is big enough, so just because one algorithm is "better" by big-O notation, doesn't mean it's the best for your application. (If the "better" one is better only when n>10,000,000 then you may find that the "inefficient" one is pretty good for your when your n is less than that, and it may be pretty hard to beat for small n.)

    Update 2: Gah! I didn't read the first one correctly and didn't see n^2 as jettero points out. Obviously I botched the first one.

    ...roboticus

    When your only tool is a hammer, all problems look like your thumb.

[reply]

      You could use a graphing calculator to show that's probably not true. n^2 log(n) will grow faster than log(n), as will n^2, so surely O(log(n)) can't be an upper bound for something that has n^2 log(n) in it. Maybe it was supposed to be n^(2 * log(n)) ... can't really tell. Probably homework anyway.

      update: lol, figured

[reply]
Re: Big O notation
by JavaFan (Canon) on Oct 15, 2011 at 04:07 UTC
    Looks like a home work problem to me. And it's void of any Perl content.

    As for your question, technically, the question is incomplete. You aren't telling us where n is going to. I'll be so bold to assume n is going towards infinity.

    Since it's a homework problem, which has nothing to do with Perl, I'm not going to give you a complete answer. Let me just say that both functions are in O(n2log log n). But that bound is tight for one of the functions, and not tight for the other. I'll leave it as an exercise to figure out which function can be estimated more tightly.

[reply]

Back to Seekers of Perl Wisdom