Discussion
Which one of the following statements is TRUE for all positive functions \(f(n)\)?
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})\).
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development