Question

Find all pairs of functions of the same order in this list of functions:${\mathit{n}}^{\mathbf{2}}\mathbf{+}{\mathbf{2}}^{\mathbf{n}}\mathbf{,}{\mathit{n}}^{\mathbf{2}}\mathbf{+}{\mathbf{2}}^{\mathbf{100}}\mathbf{,}{\mathit{n}}^{\mathbf{2}}\mathbf{+}{\mathbf{2}}^{\mathbf{2}\mathbf{n}}\mathbf{,}{\mathit{n}}^{\mathbf{2}}\mathbf{+}\mathit{n}\mathbf{!}\mathbf{,}{\mathit{n}}^{\mathbf{2}}\mathbf{+}{\mathbf{3}}^{\mathbf{n}}$ and${\mathbf{(}{\mathit{n}}^{\mathbf{2}}\mathbf{+}\mathbf{1}\mathbf{)}}^{\mathbf{2}}\mathbf{.}$

Short answer

All pairs of functions does not have same order of $O\left(n^2\right)$using the fact that nhas a higher order than $\log n$.

Step-by-step solution

Definition

Let f and g be functions from the set of integers or the set of real numbers to the set of real numbers. We say that $f\left(x\right)$ is$\Theta \left(g\right(x\left)\right)$ if$f\left(x\right)$ is$O\left(g\right(x\left)\right)$ and$f\left(x\right)$ is $\Omega \left(g\right(x\left)\right)$. When$f\left(x\right)$ is$\Theta \left(g\right(x\left)\right)$ we say thatf is big-Theta of $g\left(x\right)$, that$f\left(x\right)$ is order of$g\left(x\right)$ and that$f\left(x\right)$ and$g\left(x\right)$ are of the same order.

 Determine the order for all pairs of functions

We know that$\log n\le n$ and the Big- O estimate of the sum of terms is the Big-O terms of the highest order term

Now the order for the functions are,

$n^2+2^n$is$O\left(2^n\right)$

role="math" localid="1668603397132" $n^2+2^{100}$is$O\left(n^2\right)$

$n^2+2^{2}n$is$O\left(4^n\right)$

$n^2+n!$is$O(n!)$

$n^2+3^n$is$O\left(3^n\right)$

$(n^2+1{)}^2$is$\left(n^4\right)$

Hence all pairs of functions does not have same order.