Let f(n) = n and g(n) = n(1 + sin n), where n is a positive integer. Which of the following statements is/are correct? I. f(n) = O(g(n)) II. f(n) = (g(n))
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2015 Set 3 · Q42
Time
Select one answerSingle correct
Solution
Official answer: D) Neither I nor II
Asymptotic AnalysisHere and . The function oscillates continuously between and as .
Statement I ($f(n) = O(g(n))$):
requires that there exist constants and such that for all .
However, whenever (for infinitely many values of , ), , whereas . Thus, no such constant exists, and statement I is false.
Statement II (): requires that there exist constants and such that for all . However, whenever (for infinitely many values of , ), , which grows much faster than . Thus, no such constant exists, and statement II is false.
Hence, Neither I nor II is correct (D).
Try the question first, then check your work.
Examiner trap
Analyze the behavior of as grows large: what happens to when versus when ?
This Asymptotic Analysis previous year question is Q42 of the GATE CSE 2015 Set 3 paper. Find more GATE CSE PYQs on Asymptotic Analysis in Algorithms, or browse all GATE CSE PYQs.
Free diagnostic
Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Asymptotic Analysis PYQs now with no account.
An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.
Asymptotic Analysis has 31 GATE CSE PYQs across 19 papers from 2011 to 2026. 12 of them are 2-mark MCQs like this one, and GATE CSE 2015 Set 3 has 2.
How GATE tests Asymptotic AnalysisIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.