# Finding which functions are bounded by $O(n^2)$

I am asked to select the functions that are bounded by the Big-Oh function O(n^2): $$f(n) \in O(n^2)$$.

1. $$f(n) = \sum_{i=1}^{n} n$$
2. $$f(n) = \sum_{i=1}^{n} i$$
3. $$f(n) = n + n^2$$
4. $$f(n) = 1$$

I choose the answers 1, 2, and 4:

1. Simplifies to $$n \cdot n = n^2$$, which is bounded by $$O(n^2)$$
2. Simplifies to $$\frac{n(n + 1)}{2} = n^2/2 + 1/2$$, which is bounded by $$O(n^2)$$
3. $$n^2 + n$$ is obviously not bounded by $$O(n^2)$$
4. $$1$$ is obviously bounded by $$O(n^2)$$

However, it was alerted to me that one of my answers is incorrect. That seems strange, considering that after expanding all the expressions mathematically, I believe that I have chosen whether they are bounded by $$n^2$$ correctly.

• Are you familiar with the definition of big O? – Yuval Filmus Jan 17 at 15:59

We have $$n^2 + n = O(n^2)$$. Indeed, if $$n \geq 1$$ then $$n^2 \geq n$$ and so $$n^2 + n \leq 2n^2.$$
I know, that answer is done, is correct and is accepted, but let me add, that "function is bounded by $$O(n^2)$$" is not completely correct sentence and as such can lead to errors: $$O(n^2)$$ is set, so we can speak about boundedness by some member from it, but exact is to say, that function is bounded by some $$\boldsymbol n^{ \boldsymbol 2}$$ factor, starting from some number up to infinity.