Skip to main content
2 of 3
added 192 characters in body
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.

Edit: Yes I know I'm abusing big O notation, but writing "$\mathcal{O}(f)$ where $f(N) = N!$" wouldn't fit easily in a title and $\mathcal{O}(!)$ looks silly and confusing at first glance.

user6873235
  • 766
  • 6
  • 10