Discussion
Give as good a big-O estimate as possible for the following functions : \((n\log n+n^{2})(n^{3}+2)\) and \((n!+2^{n})(n^{3}+\log(n^{2}+1))\)
Answer: C
The first function (n log n + n^2)(n^3 + 2) is dominated by n^2 x n^3 = n^5 since n log n is smaller than n^2 and 2 is smaller than n^3, so it is O(n^5). The second, (n! + 2^n)(n^3 + log(n^2 + 1)), has n! growing faster than 2^n and n^3 faster than the logarithm, so it is O(n^3 x n!). The pair is O(n^5) and O(n^3 x n!), option (C). Options (A) and (D) keep a lower order term, 2n^2, which a big-O estimate drops, and (B) and (D) give 2^n in place of n! in the second function, which understates its growth because n! is much larger than 2^n.
No comment is present. Be the first to comment.
Loading…
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