ISRO CS 2023 Q.24: solution and answer

ISRO 2023 · CSQ.24 · 1 mark · MCQ

The asymptotic complexity of 4 functions f1, f2, f3, f4 are
f1(n) = 2^n
f2(n) = n^(3/2)
f3(n) = n log n
f4(n) = n^(log n)
Arrange them in increasing order of complexity.

(A)
f2, f3, f4, f1
(B)
f1, f2, f3, f4
(C)
f3, f2, f4, f1
(D)
f3, f1, f2, f4

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The increasing order is $f_{3}, f_{2}, f_{4}, f_{1}$ , which is option (c).

Official answer: CSource: ISRO's revised and final answer key of 16 February 2024

Compare $f_{3} (n) = n lo g n$ with $f_{2} (n) = n^{3/2}$ . Divide both by $n$ : $lo g n$ against $n^{1/2}$ . A logarithm grows slower than any positive power of $n$ , so $n lo g n = o (n^{3/2})$ . Hence $f_{3} < f_{2}$ .
Compare $f_{2} = n^{3/2}$ with $f_{4} = n^{l o g n}$ . The exponent $lo g n$ eventually exceeds $3/2$ and keeps growing, while $3/2$ is constant. So $n^{3/2} = o (n^{l o g n})$ . Hence $f_{2} < f_{4}$ .
Compare $f_{4}$ with $f_{1} = 2^{n}$ by taking logarithms (base 2): $lo g f_{4} = (lo g n) \cdot (lo g n) = (lo g n)^{2}$ and $lo g f_{1} = n$ . Since $(lo g n)^{2} = o (n)$ , we get $f_{4} < f_{1}$ .
Combining: $n lo g n < n^{3/2} < n^{l o g n} < 2^{n}$ , that is $f_{3}, f_{2}, f_{4}, f_{1}$ .
Check the options: (a) puts $f_{2}$ before $f_{3}$ , which is wrong. (b) puts the exponential first, which is wrong. (d) puts $f_{1}$ before $f_{2}$ and $f_{4}$ , which is wrong. Only (c) matches the order $f_{3}, f_{2}, f_{4}, f_{1}$ .

KEY IDEA

Compare growth rates by dividing out common factors or by taking logarithms: $lo g n$ is smaller than any power $n^{ϵ}$ , a function $n^{l o g n} = 2^{(l o g n)^{2}}$ is super-polynomial but still below $2^{n}$ because $(lo g n)^{2} = o (n)$ .

WATCH OUT FOR

Treating $n^{l o g n}$ as a polynomial and placing it below $n^{3/2}$ , or treating it as exponential and placing it above $2^{n}$ . Its exponent grows without bound, so it beats every fixed power of $n$ , yet its logarithm $(lo g n)^{2}$ is far smaller than $n$ .

From the ISRO CS 2023 paper. Every question of this paper · The full paper (PDF, ISRO) · All 2 ISRO Complexity questions, with notes