0
$\begingroup$

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)$?

$\endgroup$
  • 7
    $\begingroup$ 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. $\endgroup$ – babou Apr 12 '14 at 14:59
  • 3
    $\begingroup$ You might find our reference questions on asymptotics helpful. $\endgroup$ – Raphael Apr 12 '14 at 17:52
  • $\begingroup$ 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. $\endgroup$ – Schilcote Apr 13 '14 at 0:47
  • $\begingroup$ @Schilcote: That's a very limited point of view. What's with recursion? $\endgroup$ – Raphael Apr 14 '14 at 7:51
  • $\begingroup$ @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. $\endgroup$ – Schilcote Apr 14 '14 at 15:13
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Don't you want to use $\Theta$? $\endgroup$ – Raphael Apr 12 '14 at 15:22
  • $\begingroup$ @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. $\endgroup$ – tanmoy Apr 12 '14 at 15:39
6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

Take a look at linear speedup theorem.

Basically, it says, that for every Turing machine $M_1$ operating in time $f(n)$, and for every constant $0<c\leq 1$, you can always make a Turing machine $M_2$ solving the same problem in time $f(n) \cdot c + n + 2$. It's because of the fact, that each Turing machine can have a different work alphabet, set of states and transition relation. Each letter in $M_2$'s work alphabet can correspond to a fixed number (roughly $1/c$) of letters in $M_1$'s work alphabet. Compressing states and transitions in the same way results in a Turing machine $M_2$ that is faster by a fixed constant (after you pay the linear time to rewrite the input).

In result, you can manipulate the constant in complexity function (both time and space) as needed.

And remember, that the extra $n + 2$ term is not that important, since people don't care about algorithms that give you an answer before they read the whole input.

$\endgroup$
  • $\begingroup$ Welcome to the site! I'm slightly surprised by this answer because it's normally me that mentions the linear speedup theorem. :-) I made a couple of small edits to your answer to clarify it slightly; I hope that's OK. $\endgroup$ – David Richerby Feb 11 '17 at 10:48
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy