**Problem Detail:**

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?

###### Asked By : joanca

#### Answered By : Yuval Filmus

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.

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23363

**3.2K people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback