GATE 2011 CS (CS1) – Question 47

Algorithms · Asymptotic Analysis and Time/Space Complexity · 2 marks · Multiple choice

Find increasing asymptotic growth order for $f_1(n)=2^n$, $f_2(n)=n^{3/2}$, $f_3(n)=n\log_2n$, $f_4(n)=n^{\log_2n}$.

f₃,f₂,f₄,f₁
f₃,f₂,f₁,f₄
f₂,f₃,f₁,f₄
f₂,f₃,f₄,f₁

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) f₃,f₂,f₄,f₁

Explanation

log n grows slower than n¹ᐟ², so f₃<f₂ asymptotically. The exponent log₂n eventually exceeds every fixed constant, making f₄ superpolynomial. But $\log_2 f_4=(\log_2n)^2=o(n)=\log_2 f_1$, so f₄ remains below the exponential f₁. Thus A.

More Asymptotic Analysis and Time/Space Complexity questions

GATE 2010 CS (CS1) Q22 – Packages A,B process n=10k database records. A needs 0.0001n² time; B needs 10n 10n. Find…
GATE 2015 CS (CS2) Q16 – An unordered list contains n distinct elements. How many comparisons are needed to find…
GATE 2015 CS (CS2) Q26 – Decision problem Q1 reduces in polynomial time to 3-SAT, and 3-SAT reduces in polynomial…
GATE 2015 CS (CS3) Q20 – For i=0n i3=X, consider I (n4), II (n5), III O(n5), IV (n3). Which may replace X?
GATE 2015 CS (CS3) Q37 – Worst-case mergesort takes 30 seconds for input size 64. Which best approximates the…
GATE 2015 CS (CS3) Q41 – L1≤pL2, L3≤pL2 and L2≤pL4. Which are guaranteed? I: L4∈P implies L2∈P. II: L1∈P or L3∈P…

All Asymptotic Analysis and Time/Space Complexity questions →