GATE CSE 2022 | Question: 1

Question

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

• A. $f(n^{2}) = \theta (f(n)^{2}),$ when $f(n)$ is a polynomial
• B. $f(n^{2}) = o (f(n)^{2})$
• C. $f(n^{2}) = O (f(n)^{2}),$ when $f(n)$ is an exponential function
• D. $f(n^{2}) = \Omega (f(n)^{2})$

Comments

sir for option D we can also take a constant function right like f(n)=k

---

For option d take f(n) = 1/(e^n)

---

A polynomial of any degree \(k\) always looks like this when \(n\) goes to infinity:
\(f(n)\approx a\cdot n^{k}\)

Now substitute \(n^{2}\) on the left side, and square the whole function on the right side:

1. Left Side \(f(n^2)\): Replace \(n\) with \(n^{2}\)
   \(a\cdot (n^{2})^{k}=a\cdot n^{2k}\)
2. Right Side \([f(n)]^2\): Square the entire dominant term
   \((a\cdot n^{k})^{2}=a^{2}\cdot n^{2k}\)

Look closely at the resulting powers of \(n\). Both sides simplify to a term multiplied by \(n^{2k}\)

Because the highest exponent on both sides is exactly \(2k\) (regardless of what \(k\) or \(a\) actually are), both functions are guaranteed to be of order \(\Theta(n^{2k})\). Since they share the exact same order of growth, they are asymptotically tight:
\(f(n^{2})=\Theta \left([f(n)]^{2}\right)\)

Answer 1

Answer: A

$$ f(n^2) \text{ versus } f(n)^2 \text{ asymptotically} $$

All of these — $$ \boxed{f(n^2) > f(n)^2}, \quad \boxed{f(n^2) < f(n)^2}, \quad \boxed{f(n^2) = f(n)^2} $$ are possible, depending on the function we take for \( f(n) \).

Consider the following three cases:

---

Case 1: \( f(n) = \log n \)

$$ f(n^2) = 2\log n $$ $$ f(n)^2 = (\log n)^2 $$

⇒ \( f(n^2) < f(n)^2 \)

Case 2: \( f(n) = e^n \)

$$ f(n^2) = e^{n^2} $$ $$ f(n)^2 = e^n \cdot e^n = e^{2n} $$

⇒ \( f(n^2) > f(n)^2 \)

You can verify this by taking \(\log\) on both sides of \( e^{n^2} \) and \( e^{2n} \).

Case 3: \( f(n) = n^3 \) (polynomial)

$$ f(n^2) = (n^2)^3 = n^6 $$ $$ f(n)^2 = (n^3)^2 = n^6 $$

⇒ \( f(n^2) = f(n)^2 \)

Note: The symbols \( <, >, = \) above denote asymptotic comparison, not strict mathematical inequality.
For example: \( a < b \) means \( a = O(b) \), \( a > b \) means \( a = \Omega(b) \), \( a = b \) means \( a = \Theta(b) \) 

 

---

Option A:
$$ \boxed{f(n^2) = \Theta(f(n)^2) \text{, When \( f(n) \) is a polynomial.}} $$
✅ TRUE because of Case 3.

Option B:
$$ \boxed{f(n^2) = o(f(n)^2) \Rightarrow f(n^2) < f(n)^2} $$ ❌ False because it depends on \( f(n) \).

Option C:
$$ \boxed{f(n^2) = O(f(n)^2)} $$ When \( f(n) \) is exponential.
❌ False because, from Case 2, \( f(n^2) > f(n)^2 \).

Option D:
$$ \boxed{f(n^2) = \Omega(f(n)^2) \Rightarrow f(n^2) \ge f(n)^2} $$ ❌ False because it again depends on the nature of \( f(n) \).

---

✅ Correct Answer: Option A

Comments

how you can take logn if question say for polynomial?

 

---

@kishan2024  f(n) should be polynomial to prove either bigger or smaller we can apply logarithms! 

---

log preserves order of functions while the meaning of function remains same It's like they bring very very far functions on number line closer to each other

Answer 2

We are to determine which of the given statements is true for all positive functions $ f(n) $. Each option makes a claim involving asymptotic notation

Option A  
Statement: $ f(n^2) = \Theta(f(n)^2) $, when $ f(n) $ is a polynomial.

Let $ f(n) = a_k n^k + a_{k-1} n^{k-1} + \cdots + a_0 $, where $ a_k > 0 $ and $ k \geq 0 $. Since $ f(n) $ is a positive polynomial, its growth is dominated by the leading term $ a_k n^k $.

Then:

• $ f(n^2) = a_k (n^2)^k + \text{lower-order terms} = a_k n^{2k} + o(n^{2k}) $,
• $ f(n)^2 = (a_k n^k + o(n^k))^2 = a_k^2 n^{2k} + o(n^{2k}) $.

Thus,
$$
\lim_{n \to \infty} \frac{f(n^2)}{f(n)^2} = \frac{a_k}{a_k^2} = \frac{1}{a_k},
$$
which is a positive constant. By definition, this implies $ f(n^2) = \Theta(f(n)^2) $.

Hence, the statement holds for every positive polynomial function. The condition “when $ f(n) $ is a polynomial” is part of the statement, and under that condition, the claim is universally true.

---

Option B  
Statement: $ f(n^2) = o(f(n)^2) $.

This would require $ \lim_{n \to \infty} \frac{f(n^2)}{f(n)^2} = 0 $ for all positive $ f(n) $. Consider $ f(n) = n $. Then:

• $ f(n^2) = n^2 $,
• $ f(n)^2 = n^2 $,
• Ratio = 1, not 0.

Thus, the limit is not zero, and the statement fails. Therefore, Option B is false.

---

Option C  
Statement: $ f(n^2) = O(f(n)^2) $, when $ f(n) $ is an exponential function.

Take $ f(n) = 2^n $. Then:

• $ f(n^2) = 2^{n^2} $,
• $ f(n)^2 = (2^n)^2 = 2^{2n} $.

Since $ n^2 \gg 2n $ as $ n \to \infty $, we have $ 2^{n^2} \gg 2^{2n} $, so $ f(n^2) $ grows much faster than $ f(n)^2 $. Hence, $ f(n^2) \notin O(f(n)^2) $.

Therefore, Option C is false, even under its stated condition.

---

Option D  
Statement: $ f(n^2) = \Omega(f(n)^2) $.

This requires $ f(n^2) $ to be asymptotically at least as large as $ f(n)^2 $ for all positive $ f(n) $. Consider $ f(n) = \log n $ (positive for $ n > 1 $):

• $ f(n^2) = \log(n^2) = 2 \log n $,
• $ f(n)^2 = (\log n)^2 $.

As $ n \to \infty $, $ (\log n)^2 \gg \log n $, so $ f(n^2) = o(f(n)^2) $, and thus $ f(n^2) \notin \Omega(f(n)^2) $.

Hence, Option D is false.

 

Only Option A is correct: it is true for all positive polynomial functions

Comments

Wow, this answer is sound, the way you used the rule "when f/g coverges to a positive values as $x \rightarrow \infty$" is just so good.

Just to make it more concrete option C is gonna be True if the base of less than 1

i.e if $0 < a<1 \implies \lim_{n \rightarrow \infty}\dfrac{a^{x^2}}{a^{2x}}, \text{Let }\dfrac{1}{a} = b >1 \implies \lim_{n \rightarrow \infty}\dfrac{a^{x^2}}{a^{2x}} =\lim_{n \rightarrow \infty}\dfrac{b^{2x}}{b^{x^2}} = 0 \implies a^{x^2} = o(a^{2x}) \implies a^{x^2} = O(a^{2x}).$

The Limit goes to zero because, as $x \rightarrow \infty \implies 2x-x^2 \rightarrow -\infty \implies b^{2x -x^2} \rightarrow 0$

---

this should be the best answer!

 

---

This is very well written...

 

Answer 3

Correct  Option = A