Use limits to prove or disprove $f \in \Omega (g)$, $g \in \Theta(f)$

Question

I'm not entirely sure how to do this, but for starters I did the following:

$\lim \limits_{n \to \infty}\frac{f(n)}{g(n)}=\lim \limits_{n \to \infty}\frac{3n^2+5}{53n+9}= \infty$

So I know this means $f \in \Omega(g)$

To test whether $g \in \Theta(f)$ do I just do the following:

$\lim \limits_{n \to \infty}\frac{g(n)}{f(n)}=\lim \limits_{n \to \infty}\frac{53n+9}{3n^2+5}=0$

Answer 1

1. Proving asymptotic bounds with limits is not rigorous.

   Rigorous proves are based in the definitions of $\Omega(·)$, $\Theta(·)$, or $O(·)$ such as $$O(f) = \left\{g:\mathbb N \to \mathbb R \mid \exists n_0 \in \mathbb N,\; \exists c > 0 \text{ such that} \; \forall n \geq n_0, |f(n)| \le c|g(n)|\right\}$$ and so on.

2. In this case, it is true that $f \in \Omega(g)$, but it is false that $g \in \Theta(f)$. Here you are saying that "a linear function grows with a rate of proportionality --that is what 'being $\Theta$ of something' means-- in comparison with a quadratic function", fact that is clearly false.

3. I'll give you some equivalences useful for "normal functions" (i.e. the ones you'll find analysing algorithms). They are not rigorous and they (may) fail for strange functions --the ones that cruel mathematicians create *joke*.

   Let $f, g: \mathbb N \to \mathbb R$ be "normal functions", and the following limit, $\lim_{n \to +\infty} |f(n)/g(n)|$, is supposed to exist (it is a number in $[0, +\infty]$).

   • $f ∈ o(g) \;\iff 0 = \lim |f(n)/g(n)|$
   • $f ∈ O(g) \iff 0 ≤ \lim |f(n)/g(n)| < +∞$
   • $f ∈ \Theta(g) \iff 0 < \lim |f(n)/g(n)| < +∞$
   • $f ∈ \Omega(g) \iff 0 < \lim |f(n)/g(n)| \leq +∞$
   • $f ∈ \omega(g) \,\iff \phantom{0 \leq} \lim |f(n)/g(n)| =+ ∞$

   Note that the previous formulas are strictly true in "$\Longrightarrow$ direction" for all functions $f$ and $g$ (they do not necessarily have to be "normal functions"). However, as stated before, they are only true read in "$\Longleftarrow$ direction" for "normal functions".