1
$\begingroup$

I know this is a stupid question but I will ask it anyway. I need to do complexity analysis for n! to prove that it is not a certain complexity order. How can I go about doing that?

Problem: Prove that $n!$ is not O($2^n$).

I'm not sure how I can start this problem. I want to say that I could compare the factorial to the complexity order in an inequality. This confuses me because they are basically two different values.

  • 3
    Note that you've got a bit of the same confusion here that you've had on previous questions with respect to conflating big-O notation and _complexity_ - I strongly recommend dropping your use of the latter word entirely until you're more comfortable with the usage of the notation; I think it may be getting in the way of your understanding.2012-09-14
  • 0
    @Steven Stadnicki Do you have any good resources that can help me remove my confusion on this? I must say that my algorithms teacher is not making it very clear and my discrete teacher decided to gloss over the subject as well. So bascially in the CS side of my classes, we all just put the two together so it is hard to separate.2012-09-15
  • 0
    Michael: While I don't have any specific, I'd suggest looking at _asymptotic analysis_ as a potential starting point, as while that's often used in complexity theory it's hypothetically divorced from it. You might also look at _numerical analysis_ specifically, for instance into error estimates for solving differential equations and integrals (some magic words here are _Trapezoid Rule_, _Runge-Kutta_ and _Simpson's Rule_).2012-09-15
  • 1
    For instance, the simplest form of Taylor's Theorem essentially says that $f(x+h) = f(x)+hf'(x)+O(h^2)$ as $h\rightarrow 0$, and this has nothing to do with computational complexity at all.2012-09-15

3 Answers 3