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

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

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.
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.
• n² > n > nlogn hm. Don't think so. Not for n $\to + \infty$. – greybeard Nov 27 '19 at 20:01