Take the 2-minute tour ×
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.

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?

share|improve this question
add comment

5 Answers

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.

share|improve this answer
add comment

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.

share|improve this answer
    
This provides a great explanation of Big-O, but no explanation as to WHY we use this definition. –  jmite Feb 20 '13 at 21:03
    
As I wrote - the purpose is to simplify our lives. Be it because we don't know the exact cost of an atomic operation, or because we care about asymptotic notation. I don't find the WHY an interesting mathematical question, but rather a philosophical one. We could, technically, do without it. It would just make things really ugly and hard to work with. –  Shaull Feb 20 '13 at 21:10
add comment

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.

share|improve this answer
    
Also note that Sedgewick in his "An Introduction to the Analysis of Algorithms" advocates using o(g) as the right measure, i.e., have $\lim_{n \rightarrow \infty} \frac{g(n)}{T(n)} = 1$ as the way of describing runtimes (still in terms of dominant elementary operations if you want, but including the constant factor that bothers OP). –  vonbrand Feb 20 '13 at 19:56
add comment

$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.

share|improve this answer
2  
Actually the first $=$ is abuse of notation. $O(...)$ makes sense as set of functions in which case the first should be using $\in$, but the second is fine as it means the standard equality of sets. –  Jan Hudec Feb 20 '13 at 8:34
    
@Jan Yes, but then you ought write $f\in O(g)$ or $f\in O(n\to n^2)$. It makes senseto write $f'(x)=h(x)$ because you can evaluate the derivative in every $x$ seperately ($x$ can be considered extern to the $=$ sign). But here, you consider the whole function, therefore $n$ is interne to the $=$/$\in$ sign. –  tohecz Feb 20 '13 at 8:56
    
I usually consider $f(n)$ as just being explicit about $f$ being function of one argument. –  Jan Hudec Feb 20 '13 at 10:11
    
I usually do so as well, knowing that it is an abuse of notation as well ;) –  tohecz Feb 20 '13 at 10:24
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.