Proof of big-o propositions
We will be using the following definitions:


  Let $f\colon \mathbb{Z}_+ \to \mathbb{Z}_+$ be a function mapping positive integers to positive integers.
  
  The class $O(f)$ consists of all functions $g\colon \mathbb{Z}_+ \to \mathbb{Z}_+$ such that for some real $C&gt;0$, for all $n \in \mathbb{Z}_+$ we have $g(n) \leq Cf(n)$.
  
  The class $\Omega(f)$ consists of all functions $g\colon \mathbb{Z}_+ \to \mathbb{Z}_+$ such that for some real $c&gt;0$, for all $n \in \mathbb{Z}_+$ we have $g(n) \geq cf(n)$.
  
  The class $\Theta(f)$ consists of all functions $g\colon \mathbb{Z}_+ \to \mathbb{Z}_+$ such that for some real $C,c&gt;0$, for all $n \in \mathbb{Z}_+$ we have $cf(n) \leq g(n) \leq Cf(n)$.
  
  We also write $g(n) = O(f(n))$ instead of $g(n) \in O(f(n))$, and similarly for the other two.


These are equivalent to the more standard definition in which the above only has to hold for large enough $n$. You can also carry out the proofs below using the standard definitions &mdash; this entails only small changes.

Let's start with the second statement: $f(n) = \Theta(g(n))$ iff $g(n) = \Theta(f(n))$.

Suppose that $f(n) = \Theta(g(n))$. Then there exist $C,c&gt;0$ such that for all $n$ we have $cf(n) \leq g(n) \leq Cf(n)$. Therefore for all $n$ we have $C^{-1} g(n) \leq f(n) \leq c^{-1} g(n)$, and so $g(n) = \Theta(f(n))$. Similarly, if $g(n) = \Theta(f(n))$ then $f(n) = \Theta(g(n))$.

Now let us go back to the first statement: $O(f(n)) = O(g(n))$ iff $\Omega(f(n)) = \Omega(g(n))$ iff $\Theta(f(n)) = \Theta(g(n))$.

Suppose that $O(f(n)) = O(g(n))$. It is easy to check that $g(n) = O(g(n))$ (take $C = 1$), and so $O(f(n)) = O(g(n))$ implies that $g(n) = O(f(n))$. That is, there exists $D&gt;0$ such that $g(n) \leq Df(n)$ for all $n$. Similarly, $f(n) = O(g(n))$, and so there exists $E&gt;0$ such that $f(n) \leq Eg(n)$ for all $n$. Suppose now that $h(n) = \Theta(f(n))$. Then there exist $C,c&gt;0$ such that $cf(n) \leq h(n) \leq Cf(n)$ for all $n$. This implies that $cD^{-1} g(n) \leq h(n) \leq CEg(n)$, and so $h(n) = \Theta(g(n))$. Similarly, if $h(n) = \Theta(g(n))$ then $h(n) = \Theta(f(n))$, and so $\Theta(f(n)) = \Theta(g(n))$.

Similarly, if $\Omega(f(n)) = \Omega(g(n))$ then $\Theta(f(n)) = \Theta(g(n))$.

Conversely, if $\Theta(f(n)) = \Theta(g(n))$ then, as before, $f(n) = \Theta(g(n))$. This means that there exist $C,c&gt;0$ such that $cg(n) \leq f(n) \leq Cg(n)$ for all $n$. Now suppose that $h(n) = O(f(n))$. Then there exists $D&gt;0$ such that $h(n) \leq Df(n)$ for all $n$. Since $h(n) \leq Df(n) \leq DCg(n)$, we see that $h(n) = O(g(n))$. Similarly, if $h(n) = O(g(n))$ then there exists $E&gt;0$ such that $h(n) \leq Eg(n)$. This implies that $h(n) \leq Ec^{-1} f(n)$, and so $h(n) = O(f(n))$. Thus $O(g(n)) = O(f(n))$. Similarly, $\Omega(g(n)) = \Omega(f(n))$.