Consider the following three functions. f1 = 10n f2 = nlog n f3 = n√(n) Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2021 Set 1 · Q3
Time
Select one answerSingle correct
Solution
Official answer: D) f2, f3, f1
Asymptotic AnalysisTo compare the asymptotic growth rate of the functions, take the natural logarithm (or base-2 logarithm) of each function:
For :
For :
For :
Comparing the growth rates of their logarithms for large :
Therefore:
Thus, the increasing order of asymptotic growth rate is , which corresponds to (D).
Try the question first, then check your work.
Examiner trap
Take the logarithm of each function and compare their asymptotic growth rates.
This Asymptotic Analysis previous year question is Q3 of the GATE CSE 2021 Set 1 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. 15 of them are 1-mark MCQs like this one, and GATE CSE 2021 Set 1 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.