11
$\begingroup$

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 = ? $$

  • 3
    See http://mathoverflow.net/questions/12828/inverse-gamma-function2011-03-17
  • 1
    Do you know that the constant out in front of $n!$ is one?2011-03-17
  • 3
    Stirling's approximation, maybe?2011-03-17
  • 0
    You don't know it's one, that's why he says "approximate", presumably.2011-03-17
  • 0
    Continuing my first comment, see http://mathforum.org/kb/message.jspa?messageID=342551&tstart=02011-03-17
  • 2
    @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.2011-03-17
  • 0
    On the other hand, $n!$ grows so fast that any leading constant is not very important. But it grows so fast that for any $n \gt 20$ (say) you don't care. A $20$ item table is enough to solve the problem in the computation (as opposed to number theory) arena.2011-03-18
  • 0
    @Arturo is right. Even though Moron's answer is quite good for solving $n! = c$ approximately, one can't solve $k \cdot n! = c$ if $k$ is also unknown. @omgzor: big-O notation ignores the multiplicative constant, so if you don't know it, you can't find out the value of $n$. Also, you may want to keep in mind that theoretical computational complexity does not translate literally into practical running times, but I don't know what problem you're trying to solve here.2011-03-18
  • 0
    @Abel: I'm calculating an approximate upper bound for the size of the input on a O(n!) algorithm given that the time of the computation (t) is known.2011-03-18
  • 0
    btw, thanks muntoo for merging the questions.2011-03-18
  • 0
    @omgzor: Knowing that the algorithm has time in $O(n!)$ is not enough to calculate $n$. It depends greatly on information ignored by big-O notation. For example, $f(x) = 1000 \cdot n!$ and $g(x) = 0.000001 \cdot n!$ are both in $O(n!)$. However $f(x) = 1000$ has a solution that differs by a huge amount from that of $g(x) = 1000$, and these examples can be exaggerated: you can't even make a close guess if you don't know the multiplicative constant. You need to know more about your function, even for an approximate solution, if I'm understanding the question properly.2011-03-18

2 Answers 2

6

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.

  • 0
    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.2011-03-18
  • 1
    @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.2011-03-18
  • 0
    btw, the log on this approximation formula is base 2 right?2011-03-18
  • 0
    @omg: No. It is natural log, base e.2011-03-18
  • 0
    Thanks, I'll do a binary search to solve it as you propose.2011-03-18
1

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?

  • 0
    It's a theoretical exercise.2011-03-18