1
$\begingroup$

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.

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

2 Answers 2

2
$\begingroup$

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

2. Exactly the same answer.

$\endgroup$
3
  • $\begingroup$ I got answer from textbook,but I don't understand why question 2 is correct answer. $\endgroup$
    – ben
    Aug 24, 2017 at 17:09
  • $\begingroup$ What do you mean by "why question 2 is correct answer"? You don't understand why answer is the same? $\endgroup$
    – rus9384
    Aug 24, 2017 at 17:18
  • $\begingroup$ I thought correct answer is my answer.I have understood your meaning. $\endgroup$
    – ben
    Aug 24, 2017 at 17:21
6
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Forgot about limitless functions (in fact $\limsup$ still must work). $\endgroup$
    – rus9384
    Aug 24, 2017 at 19:25
  • $\begingroup$ @rus9384 It sure does! One can use the lim sup definitions to solve the exercise, too. $\endgroup$
    – Raphael
    Aug 24, 2017 at 19:58
  • $\begingroup$ I think it's no more $\Theta(n^2)$, as $\frac{3n^2}{\log n}$ is smaller. Ans this is a supremum. $\endgroup$
    – rus9384
    Aug 25, 2017 at 5:34
  • $\begingroup$ @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. $\endgroup$
    – Raphael
    Aug 25, 2017 at 6:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.