patternMinor
Finding which functions are bounded by $O(n^2)$
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)$.
I choose the answers 1, 2, and 4:
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.
- $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.
$$
$$
n^2 + n \leq 2n^2.
$$
Context
StackExchange Computer Science Q#134466, answer score: 2
Revisions (0)
No revisions yet.