0

I solved the following problem by plotting a graph and comparing the complexities. The picture below show the question along with my answer and the TA's corrections.

Question with my solution and TA's remarks

Can someone please tell me what I am doing wrong? I didn't understand the explanation given in class. When we plot several functions in a graph, the function that grows the fastest has the smallest value of y as compared to the other functions for the same value of x. At least that is the reasoning I am following. Please correct me if I am wrong.

Another thing that I don't understand is whether the factorial function is the fastest of all functions or not. I find it hard to believe. I've heard people claiming both sides. I found the following in our study material:

Comparison of several functions' growth

From this picture, it seems to me that n! is the slowest. Can someone confirm this?

Prachi
  • 101
  • You hear that n! is both fastest and slowest. It is the fastest growing of the functions involved, which means that if you are waiting n! seconds, it will be the longest wait, and thus gives the slowest runtime, if that makes sense. – Chris Bonnell Oct 01 '13 at 01:07
  • I think I understand what you mean. n! is fastest growing cause its value bloats up more as compared to other functions. i.e. for a given value of x, the corresponding value of y will be higher for n! as compared to other functions. And this higher value of y will take longer to compute. Hence, running time for n! is the largest. – Prachi Oct 02 '13 at 01:43

1 Answers1

1

Factorials aren't the fastest thing imaginable, but they are one of the fastest growing functions for this purpose, yes.

$n!$ can be re-represented with Stirling's approximation as $n! \sim (\frac{n}{e})^n \sqrt{2 \pi n}$. I'd recommend plugging this in and seeing what happens.

If we do, we find that $\ln(n)! \sim (\frac{\ln(n)}{e})^{\ln(n)} \sqrt{2 \pi \ln(n)} \geq n^{\ln(\ln(n))}$

Note also that $2^{2*\ln(n)} = e^{2*\ln(2)\ln(n)} = n^{2\ln(2)}$ The first form gives us that, as $n>\ln(n)$, we expect

$n! > 2^{n \ln(2)} > 2^{2\ln(n)}$ The question becomes where does $\ln(n)!$ fit in? Using our approximation and come calculus, you can see that $n^{\ln(\ln(n))} > 2^{2\ln(n)}$, giving

$n! > 2^{n \ln(2)} >\ln(n)!> 2^{2\ln(n)}$

For the bottom end, it's worth knowing (and you can figure it out with calculus) that for any $\epsilon >0$, $ln(n) = O(n^\epsilon)$, so $\ln(2\ln(n))<n^{.001}$ for sure.

The rest seems to be in place with your own logic, but that gives you the rationale for the correct ordering.

Chris Bonnell
  • 773