Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
$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.
