# Proving if $g \in \Omega (f)$ $\implies$ $g^3 \in \Omega (f^3)$

I am trying to prove if $$g \in \Omega (f)$$ $$\implies$$ $$g^3 \in \Omega (f^3)$$ where $$\forall f: N->R^+$$,$$\forall g: N->R^+$$

I tried to set $$c_4 = c_1 c_2 c_3$$ since we know that $$\exists c_4 \in R$$,$$\exists n_0 \in N$$ $$\forall n \in N$$, $$n \geq n_0$$ $$\implies g(n) \geq c_4 f(n)$$ but I am not quite sure where to go from here, or if this is the correct approach.

## 2 Answers

If we apply the formal definition then $$g(n)\in\Omega (f(n))$$ means that there exists some $$c_1>0$$ and $$n_0$$ such that

$$g(n)\geq c_1 f(n)\tag{1}$$

for all $$n>n_0 ~(n,n_0\in\mathbb N)$$.

To show that $$g(n)\in\Omega (f(n)) \implies g^3(n)\in\Omega (f^3(n))$$, we need to show that there exists some $$c_2>0$$ and $$n_0$$ such that $$g^3(n)\geq c_2 f^3(n)$$ for all $$n>n_0 ~(n,n_0\in\mathbb N)$$.

We have

$$g^3(n)\geq c_2 f^3(n)$$

so if we take the cube root of both sides then $$g(n) \geq \sqrt[\leftroot{-1}\uproot{2}3]{c_2}f(n)\tag{2}$$

By comparing $$(1)$$ with $$(2)$$, we can find a relationship between how we define $$c_1$$ and $$c_2$$.

• so you just let $c_2$ = $(c_1)^{\frac{1}{3}}$? – ph-quiett Aug 14 at 17:12
• Yes, or $(c_2)^3=c_1$. – Axion004 Aug 14 at 21:39

An alternative approach would be to apply the limit definition. We have that $$g(n)\in\Omega (f(n))$$ if

$$\liminf_{n\to\infty}\frac{g(n)}{f(n)}>0$$

so for $$g^3(n)\in\Omega (f^3(n))$$ we need to show that

$$\liminf_{n\to\infty}\frac{g^3(n)}{f^3(n)}>0$$

where

\begin{align}\liminf_{n\to\infty}\frac{g^3(n)}{f^3(n)}&=\liminf_{n\to\infty}\bigg(\frac{g(n)}{f(n)}\bigg)^3\\&=\liminf_{n\to\infty}\bigg(\frac{g(n)}{f(n)}\bigg)\liminf_{n\to\infty}\bigg(\frac{g(n)}{f(n)}\bigg)\liminf_{n\to\infty}\bigg(\frac{g(n)}{f(n)}\bigg)\end{align}

which are all $$>0$$ as $$g(n)\in\Omega (f(n))$$.