Question

Which one of the following statements is 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) \), when \( f(n) \) is an exponential function
• C. \( f(n^2) = O(f(n)^2) \), when \( f(n) \) is an exponential function
• D. \( f(n^2) = \Omega(f(n)^2) \)

Hint:

For polynomial functions, \( f(n^2) \) and \( f(n)^2 \) grow at the same rate. The notation \( \Theta \) is used for functions that grow at the same rate asymptotically.

Answer 1

The Correct Option is A

Let us analyze the given claim using asymptotic growth concepts. 

Assume \( f(n) \) is a polynomial function. Then it can be written as: \[ f(n) = \Theta(n^k) \quad \text{for some constant } k > 0. \] 

Now evaluate the two expressions: 
- \( f(n^2) = \Theta((n^2)^k) = \Theta(n^{2k}) \)  
- \( f(n)^2 = (\Theta(n^k))^2 = \Theta(n^{2k}) \) 

Thus, for polynomial functions, both \( f(n^2) \) and \( f(n)^2 \) grow at the same asymptotic rate. 

This equality of growth does **not** necessarily hold for arbitrary positive functions (for example, exponential or logarithmic functions), so the statement is only valid under the assumption that \( f \) is polynomial. 

Therefore, statement (A) is correct, while the other statements do not hold universally. 

Final Answer: (A)