Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
1  
Do you know that the constant out in front of $n!$ is one? –  cardinal Mar 17 '11 at 14:52
2  
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
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. –  cardinal Mar 17 '11 at 16:52
show 6 more comments

2 Answers

up vote 6 down vote accepted

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.

share|improve this answer
    
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
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. –  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
add comment

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?

share|improve this answer
    
It's a theoretical exercise. –  omgzor Mar 18 '11 at 15:36
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.