Question

Which of the given Options provides the increasing order of asymptotic complexity of functions f₁, f₂, f_3, and f₄?

f₁(n) = 2ⁿ f₂(n) = n^3/2 f₃(n) = n log₂ n f₄(n) = n^log₂n

1. f₃, f₂, f₄, f₁
2. f₃, f₂, f₁, f₄
3. f₂, f₃, f₁, f₄
4. f₂, f₃, f₄, f₁

Answer 1

Correct Answer - Option 1 : f₃, f₂, f₄, f₁

The correct answer is option 1

Explanation:

Taking log base 2 on all the functions

Function	Taking log	Taking a large number n = 220
f1(n) = 2n	f1(n) = n× log22 = n	f1 = 220
f2(n) = n3/2	f2(n) = 3/2 log2n	f2 = (3/2) × log2220= (3/2)× 20 =30
f3(n) = n × log2 n	f3(n) = log2 n +log2 log2 n	f3 = log2220 +log2 log2 220 = 25
f4(n) = nlog2n	f4(n) = log2 n × log2 n	f4 =  log22 20× log2 220= 20 × 20=400

 Increasing order of asymptotic complexity of functions f1, f2, f3 and f4  is f3 < f2 <f4 <​ f1