Correct answer: (A) $f(n^2)=\theta(f(n)^2)$, when $f(n)$ is a polynomial
Explanation
For a polynomial of degree $k$, $f(n^2)\sim n^{2k}$ and $f(n)^2\sim n^{2k}$, so they are $\theta$ of each other. For $f(n)=2^n$, $2^{n^2}$ is not $O(2^{2n})$. The other options fail for counterexamples such as $f(n)=1/n$ or $f(n)=2^n$.
More Asymptotic Analysis and Time/Space Complexity questions
GATE 2022 CS Q51– Consider the following recurrence: f(1)=1; f(2n)=2f(n)-1, for n1; f(2n+1)=2f(n)+1, for n1.…
GATE 2021 CS (CS1) Q13– Consider the following three functions. f 1 = 10n, f 2 = n n, f 3 = nn Which one of the…
GATE 2021 CS (CS1) Q40– Consider the following recurrence relation. T(n) = T(n/2) + T(2n/5) + 7n if n>0; T(n)=1 if…
GATE 2020 CS Q12– For parameters a and b, both of which are (1), T(n)=T(n1/a)+1, and T(b)=1. Then T(n) is
GATE 2019 CS Q47– There are n unsorted arrays: A 1,A 2,,A n. Assume that n is odd. Each of A 1,A 2,,A n…
GATE 2015 CS (CS1) Q60– An algorithm performs ( N)1/2 find operations, N insert operations, ( N)1/2 delete…