Skip to main content
1 of 3
user6873235
  • 766
  • 6
  • 10

Can $N!$ be given an expression with big-O time complexity $\mathcal{O}(N!) < N$?

The standard definition of the factorial function $N!$ is a closed form whose time complexity is $\mathcal{O}(N!) = N$. Intuitively, it would seem that this could not be improved.

However, how can we be sure? What if there is some clever equivalent definition of the function where $\mathcal{O}(N!) = \log(N)$, or $\log(\log(N))$, or $N^{0.998}$? If so, how could we know it is possible, or find an example? If not, why not?

For clarity, I'm not talking about functions whose big-O is $N!$, I'm talking about the big-O of $N!$ itself.

user6873235
  • 766
  • 6
  • 10