Which one of the following statements is TRUE for all positive functions…
2022
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) = \mathcal{O} (f(n)^2)\) - C.
\(f(n^2) = \mathcal{O} (f(n)^2)\),when\(f(n)\)is an exponential function - D.
\(f(n^2) = \Omega (f(n)^2)\)
Attempted by 252 students.
Show answer & explanation
Correct answer: A
Key idea: for polynomials the highest-degree term dominates, so squaring the polynomial and evaluating at n^2 produce the same polynomial degree and differ only by a constant factor.
Let f(n) be a polynomial of degree d with positive leading coefficient a. For large n, f(n) = a n^d (1 + o(1)).
Then f(n^2) = a n^{2d} (1 + o(1)), while (f(n))^2 = a^2 n^{2d} (1 + o(1)).
Because these two expressions differ only by the constant factor a (and lower-order terms are negligible), there exist positive constants c1, c2 and n0 such that for all n ≥ n0, c1 (f(n))^2 ≤ f(n^2) ≤ c2 (f(n))^2. Hence f(n^2) = Θ(f(n)^2).
See the option feedback for counterexamples showing why the other statements fail in general (for example, exponential and logarithmic functions).
A video solution is available for this question — log in and enroll to watch it.