Algorithm to decide if $n \le m!$

Question

This is an assignment of an introductory course of complexity theory and I need to find a way to do the following:

Given $n,m \in \Bbb N$, is $n \le m!$ ?

The idea is to provide a Post Machine that can decide this in an efficient way, using $n,m$ in a binary codification.

We know that the factorial isn't efficient, so the problem actually is just to find a way to decide this, if it's possible.

I know how to compare if $n\le m$, but the factorial is my problem. I don't how how to compute $m!$ with a Post Machine, if possible, in polynomial-time.

I guess that the most simple way to do this is comparing $n$ with factorials of numbers that are lower than $m$, but the factorial it's still my problem.

My question, is there an algorithm that can help me?

Answer 1

Here is a different solution than the one I suggested in the comments. Compute the sequence of factorials $1!,2!,3!,4!,\ldots$ until you get a number which is at least $n$. Since $(k+1)!/k! = O(\log (k!))$, you only compute numbers of magnitude $O(n\log n)$ and so of length $(1+o(1))|n|$ (here $|n|$ is the length of $n$ encoded in binary). Having found the least $k$ such that $n \leq k!$, we know that $n \leq m!$ iff $m \geq k$.

Since the sequence of factorials grows so fast, the running time isn't too bad — it's quasilinear in $|n|$ (at least in the RAM model). I'll let you work that out.