Return to Answer

The answers you give are wrong. It is easy to verify that $n, n\log n \in o(n^2)$, and similarly $n^2 \log n, n^3 \in ω(n^2)$.

Give two functions that is in $O(n^2)$ but not in $o(n^2)$.

Looking at the definitions, we see that there are two ways to come up with such a function:

• Pick any function from $\Theta(n^2)$.

  Besides the obvious candidates of the form $cn^2 + o(n^2)$, there are also more obscure ones like, for instance $2^{\sin n} \cdot n^2$.

• Pick any function $f \in O(n^2)$ for which $\lim_{n \to \infty} f(n) \cdot n^{-2}$ does not exist.

Simple examples are $(2 + \sin(n)) \cdot n^2$ and

$\qquad \displaystyle f(n) = \begin{cases}n^2, &n \in 2\mathbb{N};\\n, &n \in 2\mathbb{N}+1.\end{cases}$

There are many more.

I'll leave the proofs to you as an exercise.

The answers you give are wrong. It is easy to verify that $n, n\log n \in o(n^2)$, and similarly $n^2 \log n, n^3 \in ω(n^2)$.

Give two functions that is in $O(n^2)$ but not in $o(n^2)$.

Looking at the definitions, we see that there are two ways to come up with such a function:

• Pick any function from $\Theta(n^2)$.

  Besides the obvious candidates of the form $cn^2 + o(n^2)$, there are also more obscure ones like, for instance $ 2^{\frac{\sin n}{\log n}} \cdot n^2$.

• Pick any function $f \in O(n^2)$ for which $\lim_{n \to \infty} f(n) \cdot n^{-2}$ does not exist.

Simple examples are $(2 + \sin(n)) \cdot n^2$ or $2^{\sin n} \cdot n^2$ or

$\qquad \displaystyle f(n) = \begin{cases}n^2, &n \in 2\mathbb{N};\\n, &n \in 2\mathbb{N}+1.\end{cases}$

There are many more.

I'll leave the proofs to you as an exercise, as well as the symmetric case with $\Omega$ vs $\omega$.

The answers you give are wrong. It is easy to verify that $n, n\log n \in o(n^2)$, and similarly $n^2 \log n, n^3 \in ω(n^2)$.

Give two functions that is in $O(n^2)$ but not in $o(n^2)$.

Looking at the definitions, we see that there are two ways to come up with such a function:

• Pick any function from $\Theta(n^2)$.

  Besides the obvious candidates of the form $cn^2 + o(n^2)$, there are also more obscure ones like, for instance $\frac{2 + \sin(n)}{\log n} \cdot n^2$.

• Pick any function $f \in O(n^2)$ for which $\lim_{n \to \infty} f(n) \cdot n^{-2}$ does not exist.

Simple examples are $(2 + \sin(n)) \cdot n^2$ and

$\qquad \displaystyle f(n) = \begin{cases}n^2, &n \in 2\mathbb{N};\\n, &n \in 2\mathbb{N}+1.\end{cases}$

There are many more.

I'll leave the proofs to you as an exercise.

The answers you give are wrong. It is easy to verify that $n, n\log n \in o(n^2)$, and similarly $n^2 \log n, n^3 \in ω(n^2)$.

Give two functions that is in $O(n^2)$ but not in $o(n^2)$.

Looking at the definitions, we see that there are two ways to come up with such a function:

• Pick any function from $\Theta(n^2)$.

  Besides the obvious candidates of the form $cn^2 + o(n^2)$, there are also more obscure ones like, for instance $2^{\sin n} \cdot n^2$.

• Pick any function $f \in O(n^2)$ for which $\lim_{n \to \infty} f(n) \cdot n^{-2}$ does not exist.

Simple examples are $(2 + \sin(n)) \cdot n^2$ and

$\qquad \displaystyle f(n) = \begin{cases}n^2, &n \in 2\mathbb{N};\\n, &n \in 2\mathbb{N}+1.\end{cases}$

There are many more.

I'll leave the proofs to you as an exercise.

The answers you give are wrong. It is easy to verify that $n, n\log n \in o(n^2)$, and similarly $n^2 \log n, n^3 \in ω(n^2)$.

Give two functions that is in $O(n^2)$ but not in $o(n^2)$.

Looking at the definitions, we see that there are two ways to come up with such a function:

• Pick any function from $\Theta(n^2)$.

  Besides the obvious candidates of the form $cn^2 + o(n^2)$, there are also more obscure ones like, for instance $\bigr(2 + \frac{\sin(n)}{\log n}\bigl) \cdot n^2$.

• Pick any function $f \in O(n^2)$ for which $\lim_{n \to \infty} f(n) \cdot n^{-2}$ does not exist.

Simple examples are $(2 + \sin(n)) \cdot n^2$ and

$\qquad \displaystyle f(n) = \begin{cases}n^2, &n \in 2\mathbb{N};\\n, &n \in 2\mathbb{N}+1.\end{cases}$

There are many more.

I'll leave the proofs to you as an exercise.

The answers you give are wrong. It is easy to verify that $n, n\log n \in o(n^2)$, and similarly $n^2 \log n, n^3 \in ω(n^2)$.

Give two functions that is in $O(n^2)$ but not in $o(n^2)$.

Looking at the definitions, we see that there are two ways to come up with such a function:

• Pick any function from $\Theta(n^2)$.

  Besides the obvious candidates of the form $cn^2 + o(n^2)$, there are also more obscure ones like, for instance $\frac{2 + \sin(n)}{\log n} \cdot n^2$.

• Pick any function $f \in O(n^2)$ for which $\lim_{n \to \infty} f(n) \cdot n^{-2}$ does not exist.

Simple examples are $(2 + \sin(n)) \cdot n^2$ and

$\qquad \displaystyle f(n) = \begin{cases}n^2, &n \in 2\mathbb{N};\\n, &n \in 2\mathbb{N}+1.\end{cases}$

There are many more.

I'll leave the proofs to you as an exercise.