Where f(n) = n! belongs to? P, co-P, NPComplete or NPHard?


marked as duplicate by Raphael Mar 31 at 14:26

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ do you define $f(n)$ as a complexity function? what exactly are you asking? $\endgroup$ – lox Mar 31 at 14:07
  • 1
    $\begingroup$ Have a look at the definitions. As a starter, is "f(n) = n!" a decision problem? $\endgroup$ – Juho Mar 31 at 14:08
  • $\begingroup$ A decision problem would be "given n and x, is n! = x?" How much time would it take you to decide that? In the non-decision problem "Given n, what is n! in decimal notation", how large would be the output, compared to the size of the input? Can that problem be solved in polynomial time? $\endgroup$ – gnasher729 Mar 31 at 14:57