Question

Show that if c > d > 0 then $n^d$is$O\left(n^c\right)$but$n^c$ is notrole="math" localid="1668531864794" $O\left(n^d\right)$

Short answer

Hence,$n^d$ is$O\left(n^c\right)$ but$n^c$ is not$O\left(n^d\right)$

Step-by-step solution

Step 1:

Let $f\left(n\right)=n^d$and $g\left(n\right)=n^c$

Let k = 1

It is given that c > d > 0

We can say that c - d > 0

and n > k

$\Rightarrow \left|n^d\right|=n^d$and

$\Rightarrow \left|n^c\right|=n^c$

Also n > 1

$\Rightarrow n^{c-d}>n^d$

Using Big-O notation$n^d$ is$O\left(n^c\right)$

Step 2:

Let$f\left(n\right)=n^c$ and $g\left(n\right)=n^d$

Let k = 1

It is given that c > d > 0 and n > k

$\Rightarrow \left|n^d\right|=n^d$and

$\Rightarrow \left|n^c\right|=n^c$

Also c > d and n > 1

$\Rightarrow n^c>n^d$

Using$\left|n^d\right|=n^d,\left|n^c\right|=n^c$, and$n^c>n^d$we can say

$\left|n^d\left|<\right|n^c\right|$

Comparing the inequality with $\left|f\right(x,y\left)\right|\le C\left|g\right(x,y\left)\right|$, we get which creates C < 0 contradiction

$\Rightarrow n^c\text{is not}O\left(n^d\right)$