# 2.9

For each of the following pairs of functions, either ${\displaystyle f(n)}$ is in ${\displaystyle O(g(n))}$, ${\displaystyle f(n)}$ is in ${\displaystyle \Omega (g(n))}$, or ${\displaystyle f(n)=\Theta (g(n))}$. Determine which relationship is correct and briefly explain why.

## ${\displaystyle f(n)=\log n^{2}}$; ${\displaystyle g(n)=\log n}$ + ${\displaystyle 5}$

Answer: ${\displaystyle \log n^{2}=\Theta (\log n+5)}$

Solution:

${\displaystyle \log n^{2}=2\times \log n}$

${\displaystyle 2\times \log n\leq 2\times \log n+10}$

${\displaystyle \log n^{2}\leq 2(\log n+5)}$

${\displaystyle \log n^{2}\leq C(\log n+5)}$ (where ${\displaystyle C=2}$)

${\displaystyle \log n^{2}=O(\log n+5)}$

Also:

${\displaystyle \log n+5\leq \log n+5\log n}$

${\displaystyle \log n+5\leq 6\log n}$

${\displaystyle \log n+5\leq 3\times 2\log n}$

${\displaystyle 3\times \log n^{2}\geq \log n+5}$

${\displaystyle \log n^{2}\geq C\times (\log n+5)}$ (Where ${\displaystyle C={\frac {1}{3}}}$)

${\displaystyle logn^{2}=\Omega (\log n+5)}$

And therefore:

${\displaystyle logn^{2}=\Theta (\log n+5)}$

## ${\displaystyle f(n)={\sqrt {n}}}$; ${\displaystyle g(n)=\log(n^{2})}$

Answer: ${\displaystyle f(n)=\Omega (g(n))}$

Solution:

${\displaystyle g(n)=\log(n^{2})=2*\log(n)}$

${\displaystyle \lim _{n\to \infty }{\frac {\sqrt {n}}{2*log(n)}}=2*\lim _{n\to \infty }{\frac {\sqrt {n}}{log(n)}}=\infty }$

## ${\displaystyle f(n)=\log ^{2}(n)}$; ${\displaystyle g(n)=\log(n)}$

Answer: ${\displaystyle f(n)=\Omega (g(n))}$

Solution:

${\displaystyle \lim _{n\to \infty }{\frac {log^{2}(n)}{log(n)}}=\lim _{n\to \infty }log(n)=\infty }$

## ${\displaystyle f(n)=n}$; ${\displaystyle g(n)=\log ^{2}(n)}$

Answer: ${\displaystyle f(n)=\Omega (g(n))}$

Solution:

${\displaystyle \lim _{n\to \infty }{\frac {n}{\log ^{2}(n)}}=\lim _{n\to \infty }(({\frac {\sqrt {n}}{\log(n)}})^{2})=(\lim _{n\to \infty }{\frac {\sqrt {n}}{\log(n)}})^{2}=\infty }$

## ${\displaystyle f(n)=n*\log(n)+n}$; ${\displaystyle g(n)=\log(n)}$

Answer: ${\displaystyle f(n)=\Omega (g(n))}$

Solution:

${\displaystyle \lim _{n\to \infty }{\frac {n*\log(n)+n}{log(n)}}=\lim _{n\to \infty }({\frac {n*\log(n)}{log(n)}}+{\frac {n}{log(n)}})=\lim _{n\to \infty }(n+{\frac {n}{log(n)}})=\infty }$

## ${\displaystyle f(n)=10}$; ${\displaystyle g(n)=\log(10)}$

Answer: ${\displaystyle f(n)=\Theta (g(n))}$

Solution: Both are constants. Constants are always within a constant factor, ${\displaystyle c}$, of each other (as ${\displaystyle n\rightarrow \infty }$).

## ${\displaystyle f(n)=2^{n}}$; ${\displaystyle g(n)=10n^{2}}$

Answer: ${\displaystyle f(n)=\Omega (g(n))}$

Solution:

{\displaystyle {\begin{aligned}&\lim _{n\to \infty }{\frac {2^{n}}{10n^{2}}}\\&\implies {\frac {1}{10}}\left(\lim _{n\to \infty }{\frac {2^{n}}{n^{2}}}\right)\\&\implies {\frac {1}{10}}\left(\lim _{n\to \infty }{\frac {\ln(2)\cdot 2^{n}}{2\cdot n}}\right){\text{L'Hopital's Rule}}\\&\implies {\frac {1}{10}}\left(\lim _{n\to \infty }{\frac {2\ln(2)\cdot 2^{n}}{2}}\right){\text{L'Hopital's Rule}}\\&\implies {\frac {\ln(2)}{10}}\lim _{n\to \infty }2^{n}\\&\implies {\frac {\ln(2)}{10}}\lim _{n\to \infty }2^{n}=\infty \end{aligned}}}

## ${\displaystyle f(n)=2^{n}}$; ${\displaystyle g(n)=3^{n}}$

Answer: ${\displaystyle f(n)=O(g(n))}$

Solution:

${\displaystyle \lim _{n\to \infty }{\frac {2^{n}}{3^{n}}}=\lim _{n\to \infty }({\frac {2}{3}})^{n}=0}$

Back to Chapter 2