HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
arefindingwhichfunctionsbounded

Problem

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

  • $f(n) = \sum_{i=1}^{n} n$



  • $f(n) = \sum_{i=1}^{n} i$



  • $f(n) = n + n^2$



  • $f(n) = 1$



I choose the answers 1, 2, and 4:

  • Simplifies to $n \cdot n = n^2$, which is bounded by $O(n^2)$



  • Simplifies to $\frac{n(n + 1)}{2} = n^2/2 + 1/2$, which is bounded by $O(n^2)$



  • $n^2 + n$ is obviously not bounded by $O(n^2)$



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

Solution

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

Context

StackExchange Computer Science Q#134466, answer score: 2

Revisions (0)

No revisions yet.