Question

Show that if $b>1$and cand dare positive,then$(lo{g}_{b}n{)}^c$ is$O\left(n^d\right)$but$n^d$is not$O\left(({\log }_{b}n{)}^c\right)$

Short answer

Hence,${\left({\log }_{b}n\right)}^c\text{is}O\left(n^d\right)\text{but}{n}^d\text{is not}O\left({\left({\log }_{b}n\right)}^c\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 role="math" localid="1668532882506" $f\left(n\right)={\left({\log }_{b}n\right)}^c\text{and}g\left(n\right)=n^d$

Applying the above

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

It is given that and are positive

Let $c=d=1$and b = 2

$\begin{array}{r}\Rightarrow \underset{n\to \mathrm{\infty }}{lim} \frac{{\left({\log }_{2}n\right)}^1}{n^1}\\ \Rightarrow \underset{n\to \mathrm{\infty }}{lim} \frac{{\log }_{2}n}{n}\\ \Rightarrow \frac{1}{\mathrm{\infty }}\dots \dots \dots {\log }_{2}n<n_1\\ \Rightarrow {\left({\log }_{b}n\right)}^c\text{is}O\left(n^d\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)=n^d\text{and}g\left(n\right)={\left({\log }_{b}n\right)}^c$

Applying the above

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

It is given that and are positive

Let c = d = 1 and b = 2

role="math" localid="1668532759674" $\begin{array}{r}\Rightarrow \underset{n\to \mathrm{\infty }}{lim} \frac{n^1}{{\left({\log }_{2}n\right)}^1}\\ \Rightarrow \mathrm{\infty }\dots \dots {\log }_{2}n<n\\ \Rightarrow n^d\text{is not}O\left({\left({\log }_{b}n\right)}^c\right)\end{array}$