We have the following definitions:
$$
f(n) \in g(n) \iff \exists C\; \exists n_0\; \forall n>n_0 \text{ such that } f(n) < Cg(n) \tag 1
$$
$$A\subseteq B \iff \forall x(x \in A \implies x\in B) \tag2
$$
and the following functions:
$$f(n) = n^{2\log_2(n)}$$
$$g(n) = (n\ln(n))^2$$
$$h(n) = 3n^4$$
$$t(n) = \begin{cases}
f(n) &\quad\text{if $n$ is a prime number}\\
g(n) &\quad\text{otherwise} \\
\end{cases}$$
We have
$$0<\ln(n)\le n,\;\forall\;n \ge 3$$
because $\ln(3)<3$ and $n$ is faster growing than $\ln$ because the first derivate is larger.
Square it to get
$$0\le (\ln n)^2\le n^2,\;\forall\;n \ge 3$$
now multiply by $n^2$ to get
$$0\le (\ln n)^2 n^2 \le n^4,\;\forall\;n \ge =3$$
So you have
$$(n\ln n)^2\le n^4 \le 1\cdot 3n^4,\;\forall\;n \ge =3$$
or
$$g(n)\le 1\cdot h(n),\;\forall\;n \ge =3$$
from this and definition $(1)$, for $n_0=3$ and $C=1$ follows
$g(n)\in O(h(n))$
But $h(n)\not\in O(g(n))$. Because if there is an appropriate $C$ and $n_9$ such that
$$h(n)=3n^4 \le C (n \ln(n))^2=g(n),\forall n\ge n_0$$
We have $(\ln(n))^2<n,\; \forall n>=3$ because the inequality holds for$3$ and right side increases faster as the left side.
So if we choose $n \gt \{C,3\}$, then
$$h(n)=3n^4 = 3n^2 n n > 3n^2 C (\ln n)^2 =3Cg(n),\; \forall n\ge \max \{C,3\}$$
which is a contradiction
$$f(n)= n^{2\log_2(n)}\ge n^{2\log_2(8)} = n^6, \; \forall n\ge 8$$
therefore
$$ h(n)=3n^4\le3n^6\le3f(n),\;\forall n\ge8$$
so
from definition $(1)$ , for $n_0=8$ and $C=3$ follows $h(n)\in O(f(n))$.
We prove now, if $a$ and $b$ are two functions then
- if $a(n)\in O(b(n))$ then $O(a(n))\subseteq O(b(n))$
We prove this by using definition $(2)$. So let $d(n)\in O(a(n))$ then we have to show that $d(n)\in O(b(n))$
$d(n)\in O(a(n))$, then there is a $C_1$ and an $n_{1}$, such that
$$d(n)\le C_1 a(n),\;\forall n\ge n_{1}\tag 3$$
and $a(n)\in O(b(n))$ means there is a $C_2$ and an $n_2$, such that
$$a(n)\le C_2 b(n),\;\forall n\ge n_{2}\tag 4$$
equation $(3)$ remains valid if we replace $n_1$ by $\max\{n_1,n_2\},$ because every $n$ that is greater $\max{n_1,n_2}$ is larger than $n_1$, so we get
$$d(n)\le C_1 a(n),\;\forall n\ge \max\{n_1,n_2\}\tag 5$$
In $(3)$ we can also replace $n_2$ by $\max\{n_1,n_2\}$ and if we the multily the equation by $C_1$ we get
$$C_1a(n)\le C_1C_2 b(n),\;\forall n\ge \max\{n_1,n_2\}\tag 6$$
From these two equation follows
$$d(n)\le C_1C_2b(n),\;\forall n\ge\max{n_1,n_2}$$
So $d(n) \in O(b(n))$ according to definition $(1)$ if we choose $C=C_1C_2$ and $n_0=\max\{n_1,n_2\}$. So we have shown
$$\forall d(n)\;(d(n)\in O(a(n)) \implies d(n)\in O(b(n)))$$
according to $(2)$ this means $O(a(n))\subseteq O(b(n))$.
A well known theorem about sets is the transitivity of the $\subseteq$ relation:
- if $A\subseteq B$ and $B\subseteq C$ then $A\subseteq C$
It can be proven by using $(2)$ and I will leave this to you.
If $a\in O(b)$ and $b\in O(c)$, then $O(a)\subseteq O(b)$ and $O(b) \subseteq O(C)$. From the transitivity of the $\subseteq$ relation follows $O(a)\subseteq O(C))$ and so $a\in O(c)$.
From this we can conclude $g(n)\in O(f(n))$
We know $g \in O(f)$, so there is a $C$ and an $n_0$ such that
$$g(n)\le C_qf(n),\; \forall n\ge n_q$$
and so
$$g(n)\le C_qf(n),\; \forall n\ge n_q \text{ and } p \text{ is prime }$$
but $t(n)=g(n)$ if $n$ is a prime, so
$$t(n)\le C_1 f(n),\; \forall n\ge n_1 \text{ and } p \text{ is prime }$$
of course we have
$$f(n)\le 1\cdot f(n),\; \forall n\ge 1 \text{ and } p \text{ is not prime }$$
But $t(n)=f(n)$ for all $n$ that are not prime, so
$$t(n)\le 1\cdot f(n),\; \forall n\ge 1 \text{ and } p \text{ is not prime }$$
So finally we have
$$t(n)\le C f(n),\; \forall n\ge n_0$$
where $C=\{\max C_1,1\}$ and $n_0=\max\{n_1,1\}$
This means $t\in O(f)$.
Finally we want to show taht
$$O(h) \neq O(t)$$
If to sets are not equal then either one set is the subset of the other none of the sets is a subset of the other. The latter case applies to our inequality. There is an element in $O(h)$ that is not in $O(t)$ and there is an element in $O(t)$ that is not in $O(h)$. Actually the following is true:
- $h\not\in O(t))$ and $t \not\in O(h))$
We prove by contradiction. Assume $h\in O(h)$, then
