Is $g(n)=O(g^5(n))$ true for all functions?

[evinda]

Hey again! (Wave)

I have to determine if $g(n)=O(g^5(n))$ is true or not.

I thought that I could use the definition of Big-0h, but I don't know how to begin, formulating it.

From the definition, we have that $\exists c>0$ and $n_0 \in \mathbb{N}_0$ such that $\forall n \geq n_0$:

$$0 \leq g(n) \leq c g^5 (n)$$

I took $g(n)=\frac{1}{n}$ and in this case the relation does not stand, since we get: $n^4 \leq c$.

But, taking $g(n)=n$, the relation is true?

So, for which functions is the relation true and for which not? (Thinking)

 

[Evgeny.Makarov]

$g(n)=O(g^5(n))$ holds iff $g(n)$ is eventually separated from 0, i.e., there exist an $n_0\in\Bbb N$ and an $\varepsilon>0$ such that $g(n)>\varepsilon$ for all $n>n_0$.

 

[evinda]

$g(n)=O(g^5(n))$ holds iff $g(n)$ is eventually separated from 0, i.e., there exist an $n_0\in\Bbb N$ and an $\varepsilon>0$ such that $g(n)>\varepsilon$ for all $n>n_0$.

Could you explain it further to me? (Thinking)

 

[Evgeny.Makarov]

Prove that if $y>\varepsilon>0$ then there exists a $c$ that depends on $\varepsilon$ but not on $y$ such that $y<cy^5$. Here $y$ plays the role of $g(n)$. Obviously, if $\varepsilon\ge1$, then it is enough to take $c=1$. What happens when $0<\varepsilon<1$?

 

[evinda]

What happens when $0<\varepsilon<1$?

When $0<\varepsilon<1$, we have to take a $c>2$, right? (Thinking)

How do we conclude this:

$g(n)=O(g^5(n))$ holds iff there exist an $n_0\in\Bbb N$ and an $\varepsilon>0$ such that $g(n)>\varepsilon$ for all $n>n_0$

from the fact that if $g(n)=O(g^5(n))$, then $\exists c>0$ and $n_0 \in \mathbb{N}_0$ such that $\forall n \geq n_0$: $0 \leq g(n) \leq c g^5 (n)$ ? (Worried)

 

[Evgeny.Makarov]

When $0<\varepsilon<1$, we have to take a $c>2$, right?

Not just any $c>2$.

Note that
\[
y<cy^5\iff cy^4>1\iff c>\frac{1}{y^4}\iff y>\sqrt[4]{\frac{1}{c}}
\]
when $c,y>0$. I suggest answering the following questions, which lead to the solution.

1. If $y=0.5$, for what $c$ (at least one) do we have $cy^4>1$?
2. If $y=0.1$, for what $c$ do we have $cy^4>1$?
3. If $y=0.01$, for what $c$ do we have $cy^4>1$?
4. In general, if $0<y<1$, for what $c$ do we have $cy^4>1$? (Smile)
5. Suppose that the exact value of $y$ is not known, but it is known that $y>\varepsilon>0$. Which $c$ would guarantee that $cy^4>1$?

How do we conclude this:

$g(n)=O(g^5(n))$ holds iff there exist an $n_0\in\Bbb N$ and an $\varepsilon>0$ such that $g(n)>\varepsilon$ for all $n>n_0$

The questions above lead to a proof of the $(\Longleftarrow)$ part. In fact, both directions follow from the equivalence
\[
y<cy^5\iff y>\sqrt[4]{\frac{1}{c}}.
\]

 

[evinda]

Not just any $c>2$.

Note that
\[
y<cy^5\iff cy^4>1\iff c>\frac{1}{y^4}\iff y>\sqrt[4]{\frac{1}{c}}
\]
when $c,y>0$. I suggest answering the following questions, which lead to the solution.

1. If $y=0.5$, for what $c$ (at least one) do we have $cy^4>1$?
2. If $y=0.1$, for what $c$ do we have $cy^4>1$?
3. If $y=0.01$, for what $c$ do we have $cy^4>1$?
4. In general, if $0<y<1$, for what $c$ do we have $cy^4>1$? (Smile)
5. Suppose that the exact value of $y$ is not known, but it is known that $y>\varepsilon>0$. Which $c$ would guarantee that $cy^4>1$?

1. $c >16$
2. $c>10^4$
3. $c> 10^8$
4. $c> \frac{1}{y^4}$
5. $c>\frac{1}{\epsilon^4}$

Right? (Thinking)

 

[Evgeny.Makarov]

Yes. So if $g(n)>\varepsilon$ starting from some $N$, then taking any $c>\frac{1}{\varepsilon^4}$ guarantees that $g(n)<c(g(n))^5$ starting from the same $N$, i.e., $g(n)=O((g(n))^5)$. Conversely, using the last equivalence in post #6, if $g(n)<c(g(n))^5$ for all $n>N$, then $g(n)>\sqrt[4]{\frac{1}{c}}$ for $n>N$, so $g(n)$ is eventually separated from 0.