How to classify these subsets of order complexity?

Question

Let:

$$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}$$

Given that $O(g) \subset O(h)$, I want to find the relationship between the different sets $O$ of each function:

Here are my steps:

$$ \lim_{n \to \infty} \frac{f}{h} = \lim_{n\to\infty} \frac{n^{2\log_2(n)}} {3n^4} = \lim_{n\to\infty} n^{2\log_2(n)-4} *\frac{1}{3} = \infty \\\Rightarrow O(h) \subset O(f)$$

$$ \text{since}\; O(g)\subset O(h) \land O(h)\subset O(f) \\ \Rightarrow O(g)\subset O(f) $$

I am confused at how to proceed to find the relationship between $O(t)$ with respect to $O(g), O(h) \text{ and } O(f)$.

My guess is so following(but I am not sure at all or don't know how to prove it formally):

$$O(g) \subseteq O(t)$$

$$O(h) \neq O(t)$$ $$O(t) \subseteq O(f)$$

The definitions as I know them are down below:

$$ f(n) \in g(n) \iff \forall n>n_0 \text{ such that } f(n) < cg(n) $$

$$ O(f) \subset O(g) \iff g(n) \notin O(f) \text{ and } f(n) \in O(g) $$

Can you please help me or at least guide me? I don't know how to prove it

Thanks

Answer 1

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