Consider the following functions from positive integers to real numbers: 10, √(n), n, log2 n, (100)/(n) The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2017 Set 1 · Q4
Time
Select one answerSingle correct
Solution
Official answer: B) (100)/(n), 10, log2 n, √(n), n
Asymptotic AnalysisTo arrange the given functions in increasing order of asymptotic growth as :
as (strictly decreasing function, lowest asymptotic growth).
(constant function).
(logarithmic growth, grows faster than a constant).
(sub-linear polynomial growth, grows faster than logarithmic).
(linear growth, grows faster than ).
Thus, the correct increasing order of asymptotic complexity is:
This matches option (B).
Try the question first, then check your work.
Examiner trap
Analyze the rate of growth of each function as , noting that whereas other functions are either constant or growing.
This Asymptotic Analysis previous year question is Q4 of the GATE CSE 2017 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 it is the only one in GATE CSE 2017 Set 1.
How GATE tests Asymptotic AnalysisIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.