GATE 2022 CS – Question 11

Algorithms · Asymptotic Analysis and Time/Space Complexity · 1 mark · Multiple choice

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

$f(n^2)=\theta(f(n)^2)$, when $f(n)$ is a polynomial
$f(n^2)=o(f(n)^2)$
$f(n^2)=O(f(n)^2)$, when $f(n)$ is an exponential function
$f(n^2)=\Omega(f(n)^2)$

Practise this question in The GATE Grind →

Show answer and explanation

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$.