Compare growth of function

201 views Asked by At

I have the following:

  1. n!
  2. nlogn
  3. 2 ^ n
  4. sqrt3(n) = n^1/3
  5. n ^ 3

We know that in order to compare two functions we need lim n->infinity f(n) / g(n) But we also know that exponential > polynomial > polylogarithmic. We also know from stirling that n! = o(n^n) and n! = ω(n^2)

So the correct order of the above functions is: (from small to big) 4 -> 2 -> 5-> 3 ->1. Am i right? And do i have to find the limits in order to prove the above? Can i just take the above facts instead of finding the limits ?

1

There are 1 answers

0
templatetypedef On BEST ANSWER

Your answer is correct. As for what you need to prove or not, that really depends on the context. If this is for an algorithms paper, you can assume that everyone reading your paper would know this. If this is for a class, the best answer would be to check with the instructor or the TAs. :-)

Hope this helps!