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 = ? $$
 A: 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.
A: It also depends on the algorithm. You would need an algorithm that can translate to an "oblivious TM", a Turing Machine where the head movements depend only on the time step we are currently at. If your algorithm running time is different for different inputs of the same size, that is if you use loops that can be terminated abruptly (like when we search for one or more occurences of an item) or conditionals where each case has different running times (e.g. some heuristics), I believe approximating the input size is even more difficult.
I am however curious about your motive. Why isn't the input size known beforehand?
