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?
Tell me more
×
Computer Science Stack Exchange is a question and answer site for
students, researchers and practitioners of computer science. It's 100% free, no registration required.
|
|
||||
|
|
|
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. |
|||
|
|
|
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. |
|||||
|
|
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. |
|||
|
|
$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. |
|||||||||||
|
|
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. |
|||
|
|
