Confusion about big-O notation comparison of two functions

Question

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?

Answer 1

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

Answer 2

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.