5
$\begingroup$

On page 16 of this algorithms book, it states:

For example, suppose we are choosing between two algorithms for a particular computational task. One takes $f_1(n) = n^2$ steps, while the other takes $f_2(n) = 2n + 20$ steps (Figure 0.2).

He then goes on to say:

This superiority ... (of $f_2$ over $f_1$) ... is captured by the big-O notation: $f_2 = O(f_1)$, because ...

Now my problem is that in the original quote, he said that $f_1(n) = n^2$ steps and $f_2(n) = 2n+20$ steps, so thus $f_1 = O(n^2)$ and $f_2 = O(n)$ (big-O is defined in Section 0.3). But the second quote above states $f_2 = O(f_1)$, which means $f_2 = O(n^2)$ and contradicts his definition of big-O notation. What have I missed?

Improve this question
$\endgroup$
2
  • $\begingroup$ The $=$ is a huge abuse of notation. I wonder if it wasn't chosen over $\in$ mostly for the convenience of typing it. $\endgroup$
    – Joe
    Nov 16 '12 at 3:43
  • $\begingroup$ @Joe: likely, though there is a closely related usage along the lines of $f = a + bx + cx^2 + O(x^3)$ for Taylor series. If you consider the special case $a,b,c= 0$, it would be quite tempting to simply write $f = O(x^3)$; but it feels really awkward (though it is more correct) to write $f \in a + bx + cx^2 + O(x^3)$. The fact that physicists (and other mathematicians) routinely write this sort of thing on black/white boards more or less suggests that the difficulty of writing $\in$ isn't the entire issue either. It's a place where good usage and idiom are at odds. $\endgroup$
    – Niel de Beaudrap
    Nov 16 '12 at 16:30
11
$\begingroup$

The key thing to keep in mind here is that the equals sign in $f = O(g)$ does not behave as an equals sign usually would. The reason is that $O(g)$ is not actually a function but a set of functions. For example, you can think of $O(n^2)$ as being a set which, among many other functions, contains the functions $n$, $5 \sqrt n$, $\log^5 n$, etc. So as the appropriate way to think of $f = O(g)$ is not as equality but instead as being an element of a set: $f \in O(g)$.

So the set $O(n)$ is a subset of $O(n^2)$ since any function that is asymptotically bounded above by a multiple of $n$ is also bounded asymptotically above by a multiple of $n^2$.

Improve this answer
$\endgroup$
4
$\begingroup$

The big-O denotes an upper bound. Since $O(n)\subset O(n^2) $, we have for any function $h$ $$h=O(n)\; \Rightarrow \; h= O(n^2).$$

In other words if $g_1(n)=n$ is an asymptotic upper bound for $f_2(n)$ then $g_2(n)=n^2$ is of course also an asymptotic upper bound for $f_2(n)$. The statement does not contradict the definition of the big-O definition.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thankyou for your reply; what confuses me is what is the purpose in saying that $h = O(n) \Rightarrow h = O(n^2)$. Because we could say that $h = O(n^{2382})$ which is also an upper bound. What's the point in talking about anything but the least upper bound? $\endgroup$
    – njp
    Nov 15 '12 at 13:46
  • 2
    $\begingroup$ Well, usually you want to have good upper bounds. However, technically there is nothing wrong with it, when you say $h=O(n^{2382})$. It's just not a very strong statement. Notice that there is also the notion of $\Theta()$ which denotes a tight bound. The problem is, that it is often challenging to derive a $\Theta()$ bound, and that is why you stick to the big-O notation. $\endgroup$
    – A.Schulz
    Nov 15 '12 at 13:52
  • $\begingroup$ Sometimes we simply don't know the least upper bound. We can do matrix multiplication in $O(n^3)$, and even in $O(n^{2.38})$. It is a huge open question whether we can do it in $O(n^2)$. $\endgroup$
    – Pål GD
    Nov 15 '12 at 13:52
  • 1
    $\begingroup$ Right, so in the case described in my original question, all we're really saying is that $f_2$ has equal or less time complexity than $f_1$, but on the other hand $f_1$'s complexity is not contained in $O(f_2)$ because $f_2 = O(n)$? I think the notation is odd, maybe it should be $f_2 \in O(f_1)$. $\endgroup$
    – njp
    Nov 15 '12 at 13:57
  • 2
    $\begingroup$ @DesmondWolf: Indeed, the equality sign is slightly misleading as it is not symmetric. Membership is more correct, but when we speak about it, we really say "$f_2$ is $O(n)$", and then the equality sign seems more natural. $\endgroup$
    – Pål GD
    Nov 15 '12 at 18:23

Your Answer

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

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