What is constant factors and low-order term in algorithms?

Question

In the following video, there is an explanation of asymptotic analysis: https://class.coursera.org/algo-004/lecture/169

But I can't understand what is "low-order term" and "constant factor" itself? (it is at the 4th minute of the video).

The merge sort is 6n*log2(n)+6n. Why 6n is the low-order term and 6 is constant factor in here? Do these terms have concrete definition?

Answer 1

Lower-order term:

"Order" here refers to the order of magnitude.

The concept is easy to understand and explain when dealing with very simple terms such as x or x2. x has order of magnitude 1, since it can be written as x1, and x2 has order 2 - the order of magnitude is equal to the power of the variable in the term. But things get a little more hazy (at least for me) when you complicate things by, for example, adding log. ^[1]

In somewhat informal terms, f(x) is a lower order than g(x) if f(x) < g(x) as x tends to infinity.

It's easy to see that f(n) = 6n is a lower order than g(n) = 6n*log2(n) by just substituting some really large value for n (the correct approach is to mathematically prove it, but substituting a large value tends to work for simple terms).

The terms are essentially the things separated by plus / minus symbols.

So a lower-order term is just any term which is of a lower order than some other term.

Presumably this is the opposite of the leading-order term, which is the term with the largest order of magnitude.

[1]: I deal with big-O a lot, but it's been a while (high-school?) since I've dealt with the basics of order of magnitude, so apologies if I might have missed or forgotten something regarding that part.

Constant factor:

"Factor" is a term in multiplication. For 6n, 6 and n are factors.

A constant factor is simply anything that doesn't depend on the input parameter(s) (which is n in this case).

Here, regardless of what we make n, 6 will always stay 6, so it's constant.

Answer 2

When the function in the big-O has several terms, you can keep the one that grows faster because it "hides" the others sooner or later. And you can multiply by any constant.

O(6.N.Lg(N) + 6.N) is the same as O(6.N.Lg(N)) or O(N.Lg(N)) or O(0.01.N.Lg(N) + 42.sin(N) - 1.745 + 1/N)...

The dominant term is always N.Log(N) (and the basis of the logarithm doesn't matter).