Topic: Algorithms
The asymptotic complexity of 4 functions $f_{1}, f_{2}, f_{3}, f_{4}$ are
$f_{1}(n)=2^{n}$
$f_{2}(n)=n^{(3/2)}$
$f_{3}(n)=n \log n$
$f_{4}(n)=n^{(\log n)}$
Arrange them in increasing order of complexity
- A. $f_{2}, f_{3}, f_{4}, f_{1}$
- B. $f_{1}, f_{2}, f_{3}, f_{4}$
- C. $f_{3}, f_{2}, f_{4}, f_{1}$
- D. $f_{3}, f_{1}, f_{2}, f_{4}$
Answer: C. $f_{3}, f_{2}, f_{4}, f_{1}$
Explanation: Let's compare the growth rates:
1. $f_{3}(n) = n \log n$
2. $f_{2}(n) = n^{1.5}$. (Since $n^{1.5} > n \log n$ for large n, $f_{3} < f_{2}$)
3. $f_{4}(n) = n^{\log n}$. This grows faster than any polynomial because the exponent $\log n$ keeps increasing.
4. $f_{1}(n) = 2^{n}$. Exponential growth is faster than quasi-polynomial $n^{\log n}$.
So the order is $f_{3} < f_{2} < f_{4} < f_{1}$.