Can two function be Big-O of each other? Given two functions $f(n)$ and $g(n)$, is it possible that $f(n) = O(g)$ and that $g(n) = O(f)$? 
If the answer is yes, I have a follow-up: if $f(n)$ and $g(n)$ are Big-O of each other, does that also mean that they are Big-Omega of each other? Because if that is the case, that would mean that they are also Big-Theta of each other.
 A: 
Can two function be Big-O of each other?

The answer is yes.
One may take $f(n)=n$ and $g(n)=2n+1$, as $ n \to \infty$, one has
$$
\left|\frac{f(n)}{g(n)}\right|=\frac{n}{2n+1}\le \frac12 \implies f=O(g)
$$ and
$$
\left|\frac{g(n)}{f(n)}\right|=\frac{2n+1}{n}\le 3 \implies g=O(f).
$$
A: Is it possible? Yes. A simple example: $f=g$.
What does it imply? This is equivalent to saying that $f=\Theta(g)$. To see why:
If $f=O(g)$, there exists $c>0$ and $N \geq 0$ such that
$$
\forall n \geq N, \qquad f(n) \leq c\cdot g(n) \tag{1}
$$
If $g=O(f)$, there exists $c'>0$ and $N' \geq 0$ such that
$$
\forall n \geq N', \qquad g(n) \leq c'\cdot f(n) \tag{2}
$$
Combining (1) and (2), and choosing $M\stackrel{\rm def}{=}\max(N,N')$, $\alpha\stackrel{\rm def}{=}\frac{1}{c} > 0$, $\beta \stackrel{\rm def}{=} c'$, we get that there exist $M\geq 0$, constants $\alpha,\beta>0$ such that
$$
\forall n \geq M, \qquad \alpha f(n) \leq g(n) \leq \beta f(n) \tag{3}
$$
which by definition means $f=\Theta(g)$. This should answer both your questions.
A: The following are equivalent:


*

*$f(n) = O(g(n))$ and $g(n) = O(f(n))$

*$f(n) = \Omega(g(n))$ and $g(n) = \Omega(f(n))$ (using the definition from computational complexity theory, not the one from analytic number theory)

*$f(n) = \Theta(g(n))$.

