Question

Question: Answer each part TRUE or FALSE.

$$\begin{gathered} \mathit{a}\mathbf{.}\mathbf{2}\mathit{n}\mathbf{=}\mathit{O}\left(n\right) \\ \mathit{b}\mathbf{.}{\mathit{n}}^{\mathbf{2}}\mathbf{=}\mathit{O}\left(n\right)\mathbf{·}\mathit{A} \\ \mathit{c}\mathbf{.}{\mathit{n}}^{\mathbf{2}}\mathbf{=}\mathit{O}\left(nlog2n\right)\mathbf{·}\mathit{A} \\ \mathit{d}\mathbf{.}\mathit{n}\mathit{l}\mathit{o}\mathit{g}\mathit{n}\mathbf{=}\mathit{O}\left(n^2\right) \\ \mathit{e}\mathbf{.}\mathbf{3}\mathit{n}\mathbf{=}\mathbf{2}\mathit{O}\left(n\right) \\ \mathit{f}\mathbf{.}{\mathbf{2}}^{\mathbf{2}\mathbf{n}}\mathbf{=}\mathit{O}\left(2^{2n}\right) \end{gathered}$$

Short answer

(a) $2n=O\left(n\right)$is True.

(b)$n^2=O\left(n\right)$isFalse.

(c)$n^2=O\left(n{\log }^{2}n\right)$isFalse.

(d)$n\log n=O\left(n^2\right)$isTrue.

(e)$3n=O\left(2n\right)$isFalse.

(f)$2^{2n}=O\left(2^{2n}\right)$ is True.

Step-by-step solution

To check whether 2n = O(n)  True or false

a)$2n=O\left(n\right)$isTrue

Suppose.$c=2 2n⩽cn=2n for all n>=1$

Thus Big-O holds.

To check whether  O(n)n2=O(n) True or false

b)$n^2=O\left(n\right)$isFalse

$n^2=cn n^2<=cn for all n>=n_0$doesn’t hold.

To check whether  n2=O(nlog2n) True or false

c)$n^2=O\left(n{\log }^{2}n\right)$ isFalse

There doesn’t exist positive constants $n_0$ and c such that $n^2⩽cn {\log }^{2}n for all n>=n_0$.

To Find whether  nlogn=O(n2) True or false

d)$n\log n=O\left(n^2\right)$isTrue

$log n=O\left(n\right)$ there exist positive constants c and n0 such that log $n⩽cn for all n>=n_0$.

To Find whether  n = 2O(n) True or false

e) $3n=2O\left(n\right)$isFalse

there doesn’t exist constants c and n0 such that $3n⩽c^{2}n for all n>=n_0$.

To Find whether 22n=O(22n)  True or false

f) $2^{2n}=O\left(2^{2n}\right)$isTrue

We know any function $f\left(n\right) is O\left(f\right(n\left)\right)$.