Valid form of using Big O notation

Question

According to wiki we should use Big O notation in the following manner:

$$f(n) = O(g(x))$$

where = is read not as "equals" but "is" instead.

So, it means that if f(n) = n^2 + 2n + 5 we should note it as:

$$n^2 + 2n + 5 = O(n^2)$$

But in some articles I saw that people note it as:

$$O(n^2 + 2n + 5) = O(n^2)$$ instead

So is the latter expression is valid form or we can not note it in that way?

Answer 1

$f(n) = O(g(n))$ means that $\frac{f(n)}{g(n)}$ is bounded, hence $O(n^2 + 2n + 5) = O(2^n)$ is correct. We have more:

$$O(n^2 + 2n + 5) = o(2^n),$$

which means that $\frac{n^2+2n+5}{2^n} \to 0$$

as $ n \to \infty$.

Answer 2

The big O notation sometimes denotes a class of functions. In this sense it is true that

$$O(n^2+5n+5)=O(n^2),$$ i.e. the two classes are equivalent.

But this does not express that

$$f(n)=n^2+5n+5\in O(n^2)$$

(in other terms, there is no member "$f$" here.)

Answer 3

I think that depends on the meaning of $=$ in big O notations. We may say that $$ O(n^2+2n+5) = O(2^n) \tag {1} $$ is correct, but $$ O(2^n) = O(n^2 +2n +5) \tag{2} $$ seems problematic, because by the definition of $f = O(g)$, we would interpret $(1)$ as: for every $f$ that $|f(n)| \leqslant M|n^2 + 2n +5|$ for some constant $M > 0$ whenever $n$ is sufficiently large, we always have some constant $K > 0$ s.t. $|f(n)| \leqslant K |2^n|$ as well. This interpretation would lead us to assert that $(2)$ is not correct. So actually the $=$ here seems like $\subseteq$.

For your question, $O(n^2) = O(n^2+2n+5)$ holds and so does $O(n^2 + 2n + 5) = O(n^2)$ since $n^2 < n^2+2n+5 <3n^2$ for large $n$. Therefore this $=$ could be a real equal sign, but generally we should not assert this.

UPDATE

I might have misread the question. If you know that $f =O(g)$ or $f \in O(g)$ in a seems better notation, then clearly when $|h| \leqslant M |f|$, we have $|h| \leqslant M|f| \leqslant MK |g|$, i.e. $h \in O(g)$. Thus $O(f) = O(g)$, or $O(f) \subseteq O(g)$. Conversely if $O(f) =O(g)$ is given, then $f = O (f)$, hence $f = O(g)$, or specifically, $f \in O(f) \implies f \in O(g)$ provided that $O(f) \subseteq O(g)$.

Therefore we can write $O(n^2+2n+5) = O(n^2)$ instead of $n^2+2n + 5 = O(n^2)$.