Compare Big O Notation

Question

In n-element array sorting processing takes;
in X algorithm: 10^-8n² sec,
in Y algoritm 10^-6n log₂n sec,
in Z algoritm 10^-5 sec.

My question is how do i compare them. For example for y works faster according to x, Which should I choose the number of elements ?

Solution

When comparing Big-Oh notations, you ignore all constants:

N^2 has a higher growth rate than N*log(N) which still grows more quickly than O(1) [constant].

The power of N determines the growth rate.

Example:

O(n^3 + 2n + 10) > O(200n^2 + 1000n + 5000)

Ignoring the constants (as you should for pure big-Oh comparison) this reduces to:

O(n^3 + n) > O(n^2 + n)

Further reduction ignoring lower order terms yields:

O(n^3) > O(n^2)

because the power of N 3 > 2.

Big-Oh follows a hierarchy that goes something like this:

O(1) < O(log[n]) < O(n) < O(n*log[n]) < O(n^x) < O(x^n) < O(n!)

(Where x is any amount greater than 1, even the tiniest bit.)

You can compare any other expression in terms of n via some rules which I will not post here, but should be looked up in Wikipedia. I list O(n*log[n]) because it is rather common in sorting algorithms; for details regarding logarithms with different bases or different powers, check a reference source (did I mention Wikipedia?)

Give the wiki article a shot: http://en.wikipedia.org/wiki/Big_O_notation

Comments

[Brian J]

If you ever did any limits in calculus, it's a similar concept.

[harold]

"ignore all constants" is a bit inaccurate I would say.. constant exponents certainly aren't ignored, for one.

[Chris Dargis]

@harold: The exponent being a number does not make a term constant i.e. N^3 is not a constant, whereas 5^45 is and would be ignored.

[BlackVegetable]

Ah, I suppose you could interpret constants that way, but you are correct in saying that "constant exponents" are not ignored.

[Jim Balter]

@DougRamsey You've missed harold's point. In Big O, constant factors -- not just constant terms -- are ignored, so O(99n + 5^45) = O(n). This answer should edited to clarify just what constants are to be ignored.

[Jim Balter]

While you're right about calculating the n for which one algorithm is faster than another, the question is about Big O, which you didn't address. The problem is with the question, which asks two different things. When talking about Big O, we don't care about the precise n for which one or the other algorithm is faster, rather we want to know the rate at which the execution time increases as n grows, so we can choose the slower growing algorithm..