Justification for neglecting constant factors in Big O

Question

Many a times if the complexities are having constants such as 3n, we neglect this constant and say O(n) and not O(3n). I am unable to understand how can we neglect such three fold change? Some thing is varying 3 times more rapidly than other! Why do we neglect this fact?

Answer 1

To rationalize how asymptotic notations ignore constant factors, I usually think of it like this: asymptotic complexity isn't for comparing performance of different algorithms, it's for understanding how performance of individual algorithms scales with respect to the input size.

For instance, we say that a function that takes $3n$ steps is $O(n)$, because, roughly speaking, for large enough inputs, doubling the input size will no more than double the number of steps taken. Similarly, $O(n^2)$ means that doubling the input size will at most quadruple the number of steps, and $O(\log n)$ means that doubling the input size will increase the number of steps by at most some constant.

It's a tool for saying which algorithms scale better, not which ones are absolutely faster.

Answer 2

First, as other answers have already explained, $O(3n) = O(n)$, or to put it in words, a function is $O(3n)$ if and only if it is $O(n)$. $f = O(3n)$ means that there exists a point $N$ and a factor $C_3$ such that for all $n \ge N$, $f(n) \le C_3 \cdot 3n$. Now pick $C_1 = 3 C_3$: for all $n \ge N$, $f(n) \le C_1 \cdot n$, so $f = O(n)$. The proof of the converse is similar.

Now on to the reason why this is the right tool. Observe that when we measure the complexity of an algorithm, we don't give a unit. We don't count seconds, or machine instructions: we count some unspecified elementary steps that each take a bounded time. We do that because executing the same algorithm on a different machine would change the time needed per instruction — multiply the clock frequency by $3$ and the execution time goes from $f(n)$ to $f(n)/3$. If we implement the same algorithm in a different language, or on a different system, the time taken by each elementary step might be different, but again that's too much detail: we hardly ever care about such differences.

When you do care about precise timings, asymptotic complexity is not relevant: asymptotic complexity tells you what happens for very large input sizes, which may or may not be the actual input sizes you're dealing with.

Answer 3

Big O notation is a unit free mean of measuring performance variation, thus impervious to relative costs of computational primitives.

In a nutshell: Big O notation is a unit free, relative type of measurement (as opposed to absolute measurement). It can only measure performance variation, not absolute performance, for which constants do matter a lot. The advantage is that this makes it largely implementation independent, by allowing simpler analysis that can ignore relative costs of elementary operations, as long as these costs have positive fixed upper and lower bounds. But the consequence is that constant factors are meaningless. Still, even for its intended purpose, asymptotic complexity analysis can be questioned on other grounds, and has to be considered with care. For example, raw input size may not be the right parameter to consider.

A first remark is that your question is not quite accurately stated. When you neglect the constant $3$ in $3n$, there is indeed a "three fold change", but both vary at the same rate, and you cannot assert that "[one] thing is varying 3 times more rapidly than other".

A good reason to ignore the constant in Landau notation is that we have no unit we can rely on. When someone states that A lives twice as far from you as B does, this does have meaning independently of any unit. We can agree on it even though you measure distances in inches while I do it in light-years. But absolute distance measurement requires specifying units, and its numerical formulation depend on the chosen unit.

The actual time taken by an algorithm depends on the execution time of elementary operations, which is very machine dependent. You could count the number of elementary operations, but there is no reason to believe they all take the same time, and it is always possible to compound several operations into a single one, or conversely decompose an operation into smaller ones, so that the number of operations is not really meaningful, unless you agree on a reference virtual machine. Being reference independent is an advantage.

Another view of the advantage of the approach is that all you care in the analysis is counting the number of elementary operations, as long as their cost has an upper bound and a positive lower bound. You do not have to worry about individual cost.

However, the price to pay for that advantage is that computation cost assessment is given with unspecified unit, and computation time, for example, could be nanoseconds or millenia - we do not even try to know. In other words constant factors are meaningless, since changing units is inseparable from changing constant factor, and no reference units are used.

As noted by Patrick87, this is enough to understand how an algorithm scales with respect to input size, but it will not give an absolute measure of performance, short of relying on a reference unit. Unsing a common reference abstract machine can be done when one actually wishes to compare performance of distinct algorithms, but it is harder to make sure that the comparison is not biased by realization details. In asymptotic complexity, this risk is avoided because you compare the algorithm with itself.

Anyway, only a naive programmer would rely exclusively on asymptotic complexity to choose an algorithm. There are many other criteria, including the untold constant and the actual cost of elementary operations. Furthermore, worst case complexity can be a poor indicator, because the source of the worst case complexity can occurs rarely, and on fragments of the input small enough that it has a limited inpact. For example general parsers for Tree Adjoining Grammars have a theoretical complexity $O(n^6)$, and are quite usable in practice. The worst case I know of is the Damas-Hindley-Milner polymorphic type inference algorithm used for ML, which has exponential worst case complexity. But that does not seem to bother ML users, or to prevent the writing of very large programs in ML. There is more than the constant that matters. Actually, asymptotic analysis relates a measure of the cost of a computation to some measure of the complexity of the input. But raw size may not be the right measure.

Complexity is like decidability, it may be theoretically bad, but that may be irrelevant for most of the data space... sometimes. Asymptotic complexity analysis is a good and well designed tool, with its advantages and its limitations, like all tools. With or without expliciting the constant, which may be meaningless, using judgement is necessary.

Answer 4

Recall the definition of Big-O:

$f(n)\in O(g(n))$ iff there exists $c>0$ such that $f(n)\le cg(n)$ for all $n$.

Under this definition, we have that $dn\in O(n)$ for every constant $d$. The purpose of the $O$ notation is exactly to simplify expressions in this manner. Indeed, $3n$ grows 3 times as fast as $n$, but they are both linear. Whether this is justified or not - that depends on the context. But if you agree to use the $O$ notation, then by definition this holds.

Answer 5

The other answers provide excellent explanations of why, according to the definition of Big-O, $O(n)=O(3n)$.

As for why we actually do this in CS, it's so that we have an compact description of the efficiency of an algorithm. For example, there might be an algorithm that has an if statement, where one branch executes $n$ instructions, and the other executes $3n$ instructions. This means that the exact number changes for each input, even for inputs of the same length. We could find a number for each input, but using big-O notation gives us a measure of time complexity that holds for ALL inputs.

This is much more useful at guessing how fast an algorithm will be. Otherwise, we'd have to look at a massive piecewise function, which would be very difficult to understand.

The other main reason is so that these measurements are hardware independent. Different compilers and architectures will change the same code into very different sets of instructions. However, if we know that the number of instructions is linear, exponential, etc., then we have an idea of the algorithms speed that holds, regardless of the actual computer that we compile or run it on.

Answer 6

$f(n)=O(g(n))$ means $\limsup\limits_{n\to\infty} \frac{f(n)}{g(n)}<+\infty$.

If this is true for $g(n)=n$, this is true for $g(n)=3n$ as well, and vice versa.

Similarly, $O(n^2)=O(.00005321n^2+1000000000n+10^{46803})$. Here the equality means that $f$ belongs to the LHS iff it belongs to the RHS. The $=$ sign here is a serious abuse of notation that I personally hate, because it is confusing.

Answer 7

Let me explain you simply. Let us take n = 100000. Now, what is 3n? It is 300000 (Yeah, it is 3 folds of n) But what is n^2 ? 10000000000. ( it is 1 lakh folds of n)..Compare n^2 with n. 3 is negligible when we compare with 1 lakh. so, we can remove it.

Think if n is some billions or trillions. In this case, again we are going to compare 3 with some billions or trillions. Now, you know why we can neglect 3.