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

For polynomial functions, \( f(n^2) \) and \( f(n)^2 \) have the same growth rate. This is because both grow at a polynomial rate, and squaring \( f(n) \) is equivalent to applying the function to \( n^2 \). Hence, statement (A) is correct, and the other statements do not hold universally for all positive functions.
Final Answer: (A)