retagged by
15,469 views
36 votes
36 votes

Which one of the following statements is $\text{TRUE}$ for all positive functions $f(n)?$

  1. $f(n^{2}) = \theta (f(n)^{2}),$ when $f(n)$ is a polynomial
  2. $f(n^{2}) = o (f(n)^{2})$
  3. $f(n^{2}) = O (f(n)^{2}),$ when $f(n)$ is an exponential function
  4. $f(n^{2}) = \Omega (f(n)^{2})$
retagged by

2 Answers

Best answer
65 votes
65 votes

Answer A.

$f(n^2) \text{ versus }f(n)^2 \color{red}{\text{ asymptomatically }}$

1.Take $f(n) = logn$. $ \text{      }f(n^2) = 2logn$ and $f(n)^2  = logn logn$.
Here $\color{green}{f(n^2) < f(n)^2 }\\$
2.Take $f(n) = e^n$. $ \text{      }f(n^2) = e^{n^2}$ and $f(n)^2  = e^n e^n = e^{2n}$.
Here $\color{blue}{f(n^2) > f(n)^2 } $.
You can verify this by taking $log$ both sides in $e^{n^2}$ and $e^{2n}\\$.
3.Take $f(n)$ as polynomial say, $f(n) = n^3$.  $f(n^2) = {(n^2)^3 = n^6}$ and $f(n)^2 = {(n^3)^2 = n^6}$.
Here  $\mathbf{\color{violet}{f(n^2) = f(n)^2 }}\\ $ 

Option A.
$f(n^2)=Θ(f(n)^2)$ which is $f(n^2) =f(n)^2$.when f(n) is a polynomial function.
This is TRUE because of point 3.

Option B.
$f(n^2)=o(f(n)^2)$ which is $f(n^2) < f(n)^2$.
Obviously this is false beacuse it depends on $f(n)$.

Option C.
$f(n^2)=O(f(n)^2)$ which is $f(n^2) \leq f(n)^2$. when $f(n)$ is an exponential function.
This is false because of point 2 mentioned above.

Option D
$f(n^2)=Ω(f(n)^2)$ which is $f(n^2) \geq f(n)^2$.
Obviously this is false beacuse it depends on $f(n)$.

selected by
Answer:

Related questions

19 votes
19 votes
2 answers
1
13 votes
13 votes
5 answers
2
Arjun asked Feb 15, 2022
5,211 views
The ____________ is too high for it to be considered _____________.fair / farefaer / fairfare / farefare / fair