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.

In reply to Re: Big O notation by roboticus
in thread Big O notation by rolandomantilla

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.