# function in big O but not in little o?

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

The answer is nlogn and n,But I think a lot but can't understand why answer are them.I doubt answers is wrong.

And this question,Give two functions that is in big-omega(n^2) not in little-omega(n^2)?

The answer is n^2logn and n^3.But I think a lot but can't understand why answer are them.

• Hint: Study the definitions, and the lemmas given here.
– Raphael
Aug 24, 2017 at 18:30

Where have you got those answers?

1. Answers are wrong if that was the task. The simplest answer is $n^2$. Why? Because this function satisfies restructions: $\lim_{n\to\infty}\frac{f(x)}{n^2}>0$ (not in $o(n^2)$ requirement) and $\lim_{n\to\infty}\frac{n^2}{f(x)}>0$ (in $O(n^2)$ requirement).

• I got answer from textbook,but I don't understand why question 2 is correct answer.
– ben
Aug 24, 2017 at 17:09
• What do you mean by "why question 2 is correct answer"? You don't understand why answer is the same? Aug 24, 2017 at 17:18
– ben
Aug 24, 2017 at 17:21

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

• Forgot about limitless functions (in fact $\limsup$ still must work). Aug 24, 2017 at 19:25
• @rus9384 It sure does! One can use the lim sup definitions to solve the exercise, too.
– Raphael
Aug 24, 2017 at 19:58
• I think it's no more $\Theta(n^2)$, as $\frac{3n^2}{\log n}$ is smaller. Ans this is a supremum. Aug 25, 2017 at 5:34
• @rus9384 Damn, you are completely right. I wanted the limit to exist, which turns out to be slightly more involved. Got one now! I hope.
– Raphael
Aug 25, 2017 at 6:36