Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3 and f4 ? f1(n) = 2n f2(n) = n3/2 f3(n) = n log2 n f4(n) = nlog2 n
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2011 · Q37
Time
Select one answerSingle correct
Solution
Official answer: A) f3, f2, f4, f1
Asymptotic AnalysisTo compare the growth rates of the given functions, take the logarithm of each function:
Comparing the growth of their logarithms as :
Therefore, the increasing order of asymptotic complexity is:
Hence, the correct option is (A).
Try the question first, then check your work.
Examiner trap
Take the base-2 logarithm of all four functions to easily compare their asymptotic growth rates.
This Asymptotic Analysis previous year question is Q37 of the GATE CSE 2011 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 it is the only one in GATE CSE 2011.
How GATE tests Asymptotic AnalysisIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.