Is the following expression (on limit behaviours) correct?

Question

$$\frac{18n^4 + \mathcal{O}(n^2)}{2(n^2 + n)} \in \Omega\Big(\frac{18n^4 + \mathcal{O}(n^2)}{9n^2 - 3n}\Big).$$

I never had to analyse the limit behaviour of a function which describes itself a limit behaviour.

I don't know whether the above expression is:

1. correct
2. trivial
3. elegant

In the above I refer to $\Omega$ and $\mathcal{O}$ respectively as $$\Omega(g(n)) = \{f(n)\ |\ \exists{c, n_0 \in \mathbb{N}^\texttt{+}} :\ 0 \leq g(n) < c\cdot f(n),\ \forall n \geq n_0\},$$ $$\mathcal{O}(g(n)) = \{f(n)\ |\ \exists{c, n_0 \in \mathbb{N}^\texttt{+}}\ :\ 0 \leq f(n) < c\cdot{}g(n),\ \forall n \geq n_0\}.$$

May I have some hint?

Answer 1

Having the nested $\mathcal O(n^2)$ inside the $\Omega$ is unusual to say the least, but in this case it does not matter. For any $f \in \mathcal O(n^2)$, there is an $n_0 \in \mathbb N^+$ such that for $n \ge n_0$, $0 \le f(n) \le n^2$, which will mean that $0 \le f(n) \le n^4$. At this point, we have $$ \frac{18n^4}{2(n^2 + n)} \le \frac{18n^4 + \mathcal{O}(n^2)}{2(n^2 + n)} \le \frac{19n^4}{2(n^2 + n)} $$ and $$ \frac{18n^4}{9n^2 - 3n} \le \frac{18n^4 + \mathcal{O}(n^2)}{9n^2 - 3n} \le \frac{19n^4}{9n^2 - 3n} $$ so, up to a constant, we don't care about the $\mathcal O(n^2)$ anymore.

(Fine print: the $\mathcal O(n^2)$'s in the two parts of the expression might be different, so in general there are two thresholds $n \ge n_0$ and $n \ge n_1$ that we have to surpass. But this is fine, since it's always enough to just consider $n \ge \max\{n_0, n_1\}$.)

At this point, since $f \in \Omega(g)$ is a lower bound on $f$, it's enough to take the lower bound for one fraction and the upper bound for the other: we will be done if we prove $$ \frac{18n^4}{2(n^2 + n)} \in \Omega\left(\frac{19n^4}{9n^2 - 3n}\right). $$ (Of course, the $18$ and $19$ are both constant factors, and won't affect our work.) This is now a standard exercise in $\Omega$-notation.

Answer 2

Split it as $\frac{18n^4}{2(n^2 + n)} + \frac{O(n^2)}{2(n^2 + n)}$. The first term is $\sim 9n^2 = \Theta(n^2)$. The absolute value of the second term is for large $n$ less than or equal to $\frac{Cn^2}{2(n^2 + n)} \to C/2$, so the second term is $O(1)$. Thus the total is $\sim 9n^2$.

Answer 3

Your definition of $\Omega$ being now that of Knuth, it translates by a flip to the less ambiguous notation $\mathcal O$. All our sequences will be $>0$, to not bother about absolute values.

First recall that if $a_n\sim\lambda b_n$ and $c_n\sim\mu d_n$ for some constants $\lambda,\mu>0$, then $a\in\mathcal O(c)\iff b\in\mathcal O(d)$. The original question (correct but not so elegant) $$\frac{18n^4 + \mathcal O(n^2)}{9n^2 - 3n}\in\mathcal O\left(\frac{18n^4 + \mathcal O(n^2)}{2(n^2 + n)}\right)?$$ thus simplifies to $$\frac{n^4}{n^2}\in\mathcal O\left(\frac{n^4}{n^2}\right)?$$ which is trivial.

The simplification of each of the $\mathcal O$'s (in the two numerators) was legit because $18n^4+u_n\sim 18 n^4$ for any $u\in\mathcal O(n^2)$.