Question

Show that if dis positive and b > 1, $n^d$ is $O\left(b^n\right)$but$b^n$is not$O\left(n^d\right)$

Short answer

Hence,$n^d$ is$O\left(b^n\right)$ but$b^n$ is not _{$O\left(n^d\right)$}

Step-by-step solution

Step 1:

We know Big-O notation definition$\underset{x\to \mathrm{\infty }}{lim} \frac{f\left(x\right)}{g\left(x\right)}=C<\mathrm{\infty }$

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

Applying the above

$\Rightarrow \underset{n\to \mathrm{\infty }}{lim} \frac{{\left({\log }_{b}n\right)}^c}{n^d}$

Applying L-Hospital’s rule

$\Rightarrow \underset{n\to \mathrm{\infty }}{lim} \frac{d{n}^{d-1}}{\ln \left(b\right){\mathrm{b̸}}^n}$

It is given thatis positive

Let$d=1$

$\begin{array}{r}\Rightarrow \underset{n\to \mathrm{\infty }}{lim} \frac{1n^{1-1}}{\ln \left(b\right)b^n}\\ \Rightarrow \underset{n\to \mathrm{\infty }}{lim} \frac{1}{\ln \left(b\right)b^n}\\ \Rightarrow \frac{1}{\mathrm{\infty }}\\ \Rightarrow 0\\ \Rightarrow n^d\text{is}O\left(b^n\right)\end{array}$

Step 2:

We know Big-O notation definition$\underset{x\to \mathrm{\infty }}{lim} \frac{f\left(x\right)}{g\left(x\right)}=C<\mathrm{\infty }$

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

Applying the above

$\underset{n\to \mathrm{\infty }}{lim} \frac{b^n}{n^d}$

Applying L-Hospital’s rule

$\Rightarrow \underset{n\to \mathrm{\infty }}{lim} \frac{\ln \left(b\right){\overrightarrow{b}}^n}{d{n}^{d-1}}$

It is given thatis positive

Let d = 1

$\begin{array}{r}\Rightarrow \underset{n\to \mathrm{\infty }}{lim} \frac{\ln \left(b\right)b^n}{1n^{1-1}}\\ \Rightarrow \underset{n\to \mathrm{\infty }}{lim} \ln \left(b\right)b^n\\ \Rightarrow \mathrm{\infty }\\ \Rightarrow b^n\text{is not}O\left(n^d\right)\end{array}$