Which one of the following statements is TRUE for all positive functions \(f(n)\)?
GATE CS - 2022,
Answer: A
The true statement is \(f(n^{2}) = \theta(f(n)^{2})\) when \(f(n)\) is a polynomial.
If \(f(n)\) is a polynomial of degree \(d\) with leading coefficient \(c \gt 0\), then \(f(n^{2})\) grows like \(c\,n^{2d}\) and \(f(n)^{2}\) grows like \(c^{2} n^{2d}\). They differ only by a constant factor, so each is \(\theta\) of the other.
The others fail for some positive function. For \(f(n) = n\), \(f(n^{2}) = n^{2} = f(n)^{2}\), which is not \(o(f(n)^{2})\). For \(f(n) = 2^{n}\), \(f(n^{2}) = 2^{n^{2}}\) outgrows \(f(n)^{2} = 2^{2n}\), so it is not \(O(f(n)^{2})\). For \(f(n) = \log n\), \(f(n^{2}) = 2\log n\) grows slower than \((\log n)^{2}\), so it is not \(\Omega(f(n)^{2})\).
Please log in or register to report this question.