UPPCL AE 2018:38

Question

 

Which of the given options provides the increasing order of asymptotic complexity of functions $\text{f}_{1}, \text{f}_{2}, \text{f}_{3}$ and $ \text{f}_{4} $ ?

$\text{f}_{1} = 2^{n}, \qquad \text{f}_{2} = n^{\lg n}, \qquad \text{f}_{3} = n^{\sqrt{n}}, \qquad \text{f}_{4} = n^{2}$

• A. $\text{f}_{2}, \text{f}_{3}, \text{f}_{1}, \text{f}_{4}$
• B. $\text{f}_{4}, \text{f}_{2}, \text{f}_{3}, \text{f}_{1}$
• C. $\text{f}_{3}, \text{f}_{2}, \text{f}_{1}, \text{f}_{4}$
• D. $\text{f}_{4}, \text{f}_{3}, \text{f}_{2}, \text{f}_{1}$

Comments

Simply we can take the log and can evaluate.

Answer 1

$ f1=2^n, f2=n^(logn)  ,     f3=n^√n  ,    f4=n^2  $

lets check for large value of n i.e $2^6$

$f1=2^(64),  f2=(2^5)^6,   f3=(2^6)^8,   f4=(2^(12)) $

$f1= 2^(64),f2=2^(30) f3=,2^(48),f4=2^(12) $

Increasing Order of Asymptotic complexity:

f4<f2<f3<f1

Hence B is the correct option.