Confusion about big-O notation comparison of two functions 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?
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$.