$g \in O(f) \Rightarrow f \in O(g)$?

Question

Assume $f,g: \Bbb N \rightarrow \Bbb R $ are two functions such that $f \in \Theta(n^k)$ for some $k \in \Bbb N$ and $g \in O(f)$. Does this imply $f \in O(g)$?

We know that

$$f \in \Theta(n^k) \Rightarrow f \in O(n^k).$$

Since $g \in O(f)$, we are allowed to assume that

$$g(n) \le c \cdot f(n)$$

for some $n \in \Bbb N$ and $c > 0$. I feel like the statement can't be true, but I can't tell why. Does anyone have a hint for me?

Answer 1

We show the assumption is not true by providing a counter example. This is sufficient to answer the problem since it shows that $f\in O(g)$ does not always necessarily follow.

We consider $f:\mathbb{N}\rightarrow \mathbb{R}, f(n)=n^k$ and $g:\mathbb{N}\rightarrow\mathbb{R}, g(n)=n^{k-1}$.

At first we show that $f$ and $g$ fulfill the conditions stated in the assumption.

In order to show \begin{align*} f\in\Theta(n^k)\qquad\qquad\qquad \forall n\in\mathbb{N}\tag{1} \end{align*} we have to find constants $c_1,c_2>0$ with \begin{align*} c_1 n^k<f(n)<c_2 n^k\qquad\qquad \forall n\in\mathbb{N}\tag{2} \end{align*}

Note that we consider in (2) the complete domain $\mathbb{N}$, since there is no side-condition given on $n$. We take $c_1=\frac{1}{2}$ and $c_2=2$ and we obtain with $f(n)=n^k$ \begin{align*} \frac{1}{2} n^k<n^k<2 n^k\qquad\qquad \forall n\in\mathbb{N} \end{align*} and (1) follows.

In order to show that $g\in O(f)$ we have to find a constant $C>0$ so that \begin{align*} |g(n)|<C |f(n)|\qquad\qquad \forall n\in\mathbb{N} \end{align*} Taking $C=2$ does the job, since \begin{align*} n^{k-1}<2n^k\qquad\qquad\qquad \forall n\in\mathbb{N} \end{align*}

Conclusion: Given $f:\mathbb{N}\rightarrow\mathbb{R}, f(n)=n^k$ and $g:\mathbb{N}\rightarrow\mathbb{R}, g(n)=n^{k-1}$, we have $f\in\Theta(n^k)$, $g\in O(f)$, but this does not imply $f\in O(g)$, since \begin{align*} n^{k}\not\in O(n^{k-1})\qquad\qquad \forall n\in\mathbb{N} \end{align*}