The increasing order of following functions in terms of asymptotic complexity is:(A) f1(n) < f4(n) < f2(n) < f3(n)(B) f1(n) < f2(n) < f3(n) < f4(n)(C) f2(n) < f1(n) < f4(n) < f3(n)(D) f1(n) < f2(n) < f4(n) < f3(n)I saw this question on GeeksQuiz but I am unable to understand its answer. The correct answer is D.I think that f(2) will have the highest complexity among all because for a given number it will give the maximum output. Please help and explain how is it solved?
How to solve this asymptotic complexity problem?
algorithm analysis;time complexity;asymptotics
$f_3(n)$ has the highest asymptotic time since it is an exponential function. Although it is $(1+\epsilon)^n$ and might seem very tiny in terms of growth, there exists a real number $m$ where it grows faster than the rest.Then, we have $f_4(n)$ as quadratic function.$f_2(n)$ is unfortunately linear. Which means, it does not grow as fast as $f_4(n)$ and $f_2(n)$. Actually, while considering asymptotic growing, you should ignore the constants in the function. Thus, we can say that $O(1000000n) = O(n)$.The tricky part is $f_1(n)$. It would grow faster than $f_2(n)$ if it was $O(n \log n)$. However, it is $O(n^{1-\epsilon} \log n)$, which makes it grow slower than a linear function.