What is constant factors and low-order term in algorithms?
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).
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.