1
$\begingroup$

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

Improve this question
$\endgroup$
  • 2
    $\begingroup$ 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)$. $\endgroup$ – plop Sep 4 '20 at 10:38
  • $\begingroup$ 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. $\endgroup$ – 6005 Sep 4 '20 at 13:01
1
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Leks Sep 4 '20 at 10:22
  • $\begingroup$ 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. $\endgroup$ – Steven Sep 4 '20 at 11:02
  • $\begingroup$ 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. $\endgroup$ – STanja Sep 4 '20 at 14:15
  • 1
    $\begingroup$ @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)$. $\endgroup$ – vonbrand Sep 4 '20 at 19:31
  • $\begingroup$ @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) $\endgroup$ – JimN Sep 5 '20 at 1:38
1
$\begingroup$

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

Improve this answer
$\endgroup$

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.