Question

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

Short answer

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

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 that fis 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+(logn{)}^2$ is $O\left(n^2\right)$

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

$n^2+log{2}^n+1=n^2+nlog2+1$is $O\left(n^2\right)$

$(n+1{)}^3-(n-n{)}^3=(n^3+3n^2+3n+1)-(n^3-3n^2+3n-1)$

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

$n^2+(logn{)}^2=n^2+2nlogn+(logn{)}^2$is$O\left(n^2\right)$

Hence all pairs of functions have same order of $O\left(n^2\right)$.