# Can $n = O(n^2)$?

I'm reading Data Structures and Algorithms by Goodrich. The explanation that he gives for Big Oh notation is given below:

Let $$f(n)$$ and $$g(n)$$ be functions mapping positive integers to positive real numbers. We say that $$f(n)$$ is $$O(g(n))$$ if there is a real constant $$c > 0$$ and integer constant $$n_0\geq1$$ such that $$|f(n)| \leq cg(n)$$, for $$n\geq n_0$$. This definition is referred to as the "big-oh" notation, and is sometimes pronounced as "$$f(n)$$ is big-oh of $$g(n)$$".

If I understood this definition right, it would mean that I can say; for a function $$f(n) = n$$ then $$n$$ is big-oh of $$n^2$$ because $$n \leq 1\cdot n^2$$ for any $$n_0$$. But, that is not accurate because big-oh notation for a function '$$n$$' is $$O(n)$$. What am I missing here? Would it be accurate for me to say that '$$n$$' is big-oh of $$n^2$$?

• It causes less confusion to say that "$f$ is a $O(g)$" or what is the same $f\in O(g)$. Here $O(g)$ is the set of all functions (over the integers in this case) that satisfy your definition. You have that the identity function $f(n)=n$ satisfies $f\in O(n)$ and it also satisfy $f\in O(n^2)$. The two sets intersect and $f\in O(n)\cap O(n^2)$.
– plop
Sep 4 '20 at 10:38
• It is actually true that $n$ is big oh of $n^2$, in most formal texts. It is just that in informal usage, people don't say this because people often use big oh to mean big theta, not big oh.
– 6005
Sep 4 '20 at 13:01

The statement $$n = O(n^2)$$ is true. There is nothing wrong with it. Maybe you're thinking of the Theta notation.

• Would it be accurate to represent the big-oh notation of a linear algorithm as O(n^2)? Shouldn't big-oh notation place a tight upper bound on the function?
– Leks
Sep 4 '20 at 10:22
• It would be accurate. Saying that $f(n)=O(g(n))$ just tells you that, asymptotically, $g(n)$ is some upper bound to $f(n)$, up to multiplicative constants and lower-order additive terms. As you can see from the definition, there is no need for $g(n)$ to be tight. Perhaps you are interested in the big Omega and Theta notations from the reference I posted. In your case, the statement $n=\Theta(n)$ is correct but $n=\Theta(n^2)$ is not. Sep 4 '20 at 11:02
• It is encouraged, however, to make the big O bound as tight as reasonably possible. It does not make much sense to give an algorithm that clearly runs in $\Theta(n^3)$ but give it a running time of $O(n^5)$, instead $O(n^3)$ would be the preferred running time. Sep 4 '20 at 14:15
• @STanja, no "encouragement" at all. $O(\cdot)$ expresses one thing, use it to say that. If you want to express "tight", use $\Theta(\cdot)$ or (even better) $f(n \sim g(n)$. Sep 4 '20 at 19:31
• @STanja it is done all the time. sometimes it is hard to give the tightest big-O runtime, and so a coarse one is given instead. Yes, you're right that if one is "clearly" Theta n^3, then it wouldn't be described as O(n^5) but it's not always "clear". Bottom line is the big-O is an upper bound, so n is definitely O(n^2)
– JimN
Sep 5 '20 at 1:38

Firstly let me bring little more exactness. In sentence

If I understood this definition right, it would mean that I can say; for a function $$f(n) = n$$ then $$n$$ is big-oh of $$n^2$$ because $$n \leq 1\cdot n^2$$ for any $$n_0$$.

is used "any $$n_0$$", but in definition of $$O$$ we have $$\exists n_0$$ - existence is essential.

To clear your doubts, hope, will be helpful, if you look at $$O(n)$$ as set of functions. $$O(n^2)$$ is also set of functions, but more wide. So $$O(n) \subset O(n^2)$$. And of course as $$f(n)=n \in O(n)$$, then also $$f(n)=n \in O(n^2)$$.

By the way, we can say, than for any $$k\geqslant 2, k \in \mathbb{N}$$ is true $$f(n)=n \in O(n^k)$$, but this is not more accurate in sense, that we went to more wide set of functions $$O(n) \subset O(n^k)$$. Most accurate for $$n$$, in this sense, is $$O(n)$$.