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.

Suppose I have an algorithm that has a performance of $O(n + 2)$. Here if n gets really large the 2 becomes insignificant. In this case it's perfectly clear the real performance is $O(n)$.

However, say another algorithm has a performance of $O(n^2/2)$. Here if n gets really large then $n^2/2$ is exactly half of $n^2$, which is not significantly smaller than $n^2$. So why we drop 1/2 from $O(n^2/2)$ and it becomes $O(n^2)$?

share|improve this question
6  
Maybe you should look very quickly at the definition ... in wikipedia for example. The answer is obvious. .... unless your question is : why is big O defined the way it is? ... which does not seem clear from the statement of your question. –  babou Apr 12 at 14:59
3  
You might find our reference questions on asymptotics helpful. –  Raphael Apr 12 at 17:52
    
The answers already here are good, but I just wanted to add that it might be helpful to think of the Big O equation as solving for iterations of loops (that is, how many times the loop repeats) instead of operations. That isn't really accurate either, of course, but it's closer to the truth. –  Schilcote Apr 13 at 0:47
    
@Schilcote: That's a very limited point of view. What's with recursion? –  Raphael Apr 14 at 7:51
    
@Raphael It most definitely is, but I found that was the best way to think of it before I knew enough to actually properly understand it. And recursion is really just a fancy loop, especially when it boils down to machine code. –  Schilcote Apr 14 at 15:13

3 Answers 3

up vote 1 down vote accepted

Big-O notation only describes the growth rate of algorithms in terms of mathematical function, rather than the actual running time of algorithms on some machine. As growth rate of function $f(n)=n^2$ is same as the growth rate of the function $g(n)=n^2/2$, we can say f(n) and g(n) both belongs to the same complexity set. See How:

Mathematically, Let $f(x)$ and $g(x)$ be positive for $x$ sufficiently large. We say that $f$ and $g$ grow at the same rate as $x$ tends to infinity, if

$\qquad\displaystyle \lim_{x \to \infty} \frac{f(x)}{g(x)} = M$

for some $M \in \mathbb{R} -\{0\}$.

Now let $f(x)=x^2$ and $g(x)=x^2/2$, then $\lim_{x \to \infty} f(x)/g(x)=2$. Thus $x^2$ and $x^2/2 $ both have same growth rate and we can say $O(x^2/2)=O(x^2)$.

share|improve this answer
    
Don't you want to use $\Theta$? –  Raphael Apr 12 at 15:22
    
@Raphael: yes that would be more appropriate.but as OP asked the question in context of Big O, I used Big O to help understand the fact. –  tan Apr 12 at 15:39

When we evaluate complexity of algorithms, we count the number of computation steps, or of memory locations. But these costs are in arbitrary units. For example we have no idea how long it takes on computer X to actually execute one step of the algorithm. If you double the computer speed, you divide the time taken by 2, independently of the complexity formula, of the big-O complexity.

Hence this complexity is meaningful only up to a constant.

Hence, the 1/2 factor you mention is irrelevant. It is just the same as changing the computer, or changing the time unit. If you count in hours rather than seconds, you can get a whooping improvement factor of 3600. But you wait just as long to get the answer.

Here I did not mention that since it is supposed to be an asymptotic estimate, we first remove all that is asymptotically negligible

Another useful aspect of this definition of big-O is that you can ignore in the analysis the fact that some computations steps are more expensive than others. As long as there is a bound to the cost ratio between steps, they can simply be all considered costing the same. This can impact the total time only by a constant factor. It does make complexity analysis simpler.

share|improve this answer

Let $f(n)=\cal{O}(n^2/2)$. By definition this means there are constants $c>0$ and $n_0$ such that for all $n \geq n_0$ we have $f(n) \leq c (n^2/2)$.

So $f(n) \leq c/2 \cdot n^2 = c' \cdot n^2$, where $c'=c/2$.

So there is a constant $c'>0$ and $n_0$ such that for all $n\geq n_0$

$f(n) \leq c' \cdot n^2$.

This means $f(n) = \cal{O}(n^2)$.

share|improve this answer

Your Answer

 
discard

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