0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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}\scriptstyle 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$.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.