The typical way to compute the factorial would take $O(n)$ because it calls itself recursively. However, there are many other ways to compute the factorial function based off the gamma function, bessel functions and whatnot. So how would you prove factorial always takes at least $O(n)$ time, no matter how you choose to calculate it? Or can it be done in $O(1)$?

  • 4
    $\begingroup$ In which model? What do you count as unit operation? $\endgroup$ – Evil Oct 16 '17 at 7:35
  • $\begingroup$ Multiplication. $\endgroup$ – mtheorylord Oct 16 '17 at 7:38
  • 2
    $\begingroup$ If you are only allowed to use multiplication, I don't see how you can compute the Gamma function directly. Perhaps you had a more refined model in mind? How about one in which the Gamma function is a primitive operation having unit cost? $\endgroup$ – Yuval Filmus Oct 16 '17 at 7:55
  • $\begingroup$ No, I am asking the question over all possible algorithms. I just gave the gamma function as an example of a way to compute $n!$. I am interested in how exactly you would go about proving this, $\endgroup$ – mtheorylord Oct 16 '17 at 7:57
  • 3
    $\begingroup$ The unit-cost model is useless here. The output size alone, in bits, is growing quickly. $\endgroup$ – Raphael Oct 16 '17 at 8:07

Your Answer

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

Browse other questions tagged or ask your own question.