1
$\begingroup$

The increasing order of following functions in terms of asymptotic complexity is: complexity problem

(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?

$\endgroup$
1
$\begingroup$

$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.

$\endgroup$
  • $\begingroup$ is it true that exponential function will always have the highest asymptotic time? $\endgroup$ – TheHungryCoder Nov 10 '16 at 11:16
  • $\begingroup$ @DeepanshuGabba compared to linear, logarithmic, and polynomial, yes it will always have the highest growth rate. $\endgroup$ – padawan Nov 10 '16 at 11:18
  • $\begingroup$ Remember that this is about asymptotic behaviour. You can ask yourself: For which n is f3 (n) > f1 (n), for example, and that will be a very, very large n. You can also ask yourself: How large is f4 (n) when f3 (n) > f4 (n). These are useful things to know in practice, but the question was for asymptotic behaviour. $\endgroup$ – gnasher729 Nov 10 '16 at 11:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.