1
$\begingroup$

How can it be shown that the expression $O(n^2 + n) + \Omega (n^2 + n \log n)$ simplifies to $\Omega (n^2)$? Why is it not $\Theta(n^2)$?

$\endgroup$
0
$\begingroup$

The expression that you write means what can we say about $f(n) + g(n)$ such that $f(n) \in O(n^2 + n)$ and $g(n) \in \Omega(n^2 + n \log n)$. First, we can rewrite the inputs to $f(n) \in O(n^2)$ and $g(n) \in \Omega(n^2)$. Hence, the we can say $f(n) + g(n) \in \Omega(n^2)$.

However, we cannot say $f(n) + g(n) \in \Theta(n^2)$. As a counterexample, $f(n) = n$ and $g(n) = n^3$.

Anyhow, if you want to say there is a function $f(n)$ such that it is in $O(n^2 + n)$ and also in $\Omega(n^2 + n \log n)$, you're right. Although if $f(n) \in \Theta(n^2)$, it is in $\Omega(n^2)$ as well.

$\endgroup$
0
$\begingroup$

Remember that $f(n) = O(g(n))$ when $\lim\sup\limits_{n\rightarrow\infty}$ $\frac{f(n)}{g(n)}$ $ < \infty \space \space$ and that $f(n) = \Omega(g(n))$ when $\lim\inf\limits_{n\rightarrow\infty}$ $\frac{f(n)}{g(n)}$ $ > 0 $.

From the above expression we can eliminate both $n$ and $nlogn$ because $n^2 > n > nlogn $. We are left with $O(n^2) +\Omega(n^2)$. Since the first is a superior limit and the last an inferior limits, we know that the expression reduce to his inferior limits.

$\endgroup$
1
  • $\begingroup$ n² > n > nlogn hm. Don't think so. Not for n $\to + \infty$. $\endgroup$ – greybeard Nov 27 '19 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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