Simplify the asymptotic expressions $O(n^2 + n) + \Omega (n^2 + n \log n)$

Question

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)$?

Answer 1

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.

Answer 2

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.