$g \in O(f) \Rightarrow f \in O(g)$? 
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?
 A: 
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*}

