Question

Show that if c > b > 1then$b^n$is$O\left(c^n\right)$but$c^n$is not$O\left(b^n\right)$

Short answer

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

Step-by-step solution

Step 1:

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

Let k = 1

It is given that c > b > 1

We can say that$c^n>b^n$

and$n>k$

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

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

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

$c^n>b^n$

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

Step 2: 

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

It is given that$c>b>1$

We can say that$c^n>b^n$

and$n>k$

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

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

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

$\left|c^n\right|>\left|b^n\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 contradiction

$\Rightarrow C^n$is not$O\left(b^n\right)$