# Given $n! = c$, how to find $n$?

I'm dealing with a time-complexity problem in which I know the running time of an algorithm:

$$t = 1000 \mathrm{ms} .$$

I also know that the algorithm is upper bounded by $O(n!)$.

I want to know the approximate size of the input $n$ based on this:

$$f(n) = n! = t$$ $$f^{-1}(t) = n = ?$$

-
–  Shai Covo Mar 17 '11 at 14:43
Do you know that the constant out in front of $n!$ is one? –  cardinal Mar 17 '11 at 14:52
Stirling's approximation, maybe? –  Arturo Magidin Mar 17 '11 at 15:00
You don't know it's one, that's why he says "approximate", presumably. –  leif Mar 17 '11 at 15:05
@leif, my point was that without the constant, you only know the size up to a scale factor. So, if the OP is looking for a bound (which is what I would consider more akin to "approximate"), then he needs to know the leading constant or have some handle on it. –  cardinal Mar 17 '11 at 16:52

You can use Stirling' approximation formula:

$$\log n! = n\log n - n + \log (2\pi n)/2 + \mathcal{O}(1/n)$$

So you can take the approximation as

$$\log n! \approx n\log n - n + \log (2\pi n)/2$$

Now given $n! = c$, you can compute an approximate value for $n$ by doing a simple binary search on the above formula.

If you want a direct formula to compute and approximate value for $n$, Shai Covo has given you a link to a mathoverflow thread.

-
Thanks, but could you elaborate? I don't understand how I would apply a binary search on the formula or how the inverse Gamma function would be applied, I'm not familiar with it. –  omgzor Mar 18 '11 at 15:41
@omg: Start with an estimate of $n=1$ and keep doubling your estimate till you go over $\log(c)$. It is as if you have an infinite sorted array where the $n^{th}$ element is given by that formula, and you are searching for $\log(c)$ in that array. –  Aryabhata Mar 18 '11 at 15:46
btw, the log on this approximation formula is base 2 right? –  omgzor Mar 18 '11 at 15:50
@omg: No. It is natural log, base e. –  Aryabhata Mar 18 '11 at 15:50
Thanks, I'll do a binary search to solve it as you propose. –  omgzor Mar 18 '11 at 15:53