1

What is the largest $n\in \mathbb{R}$ for which one can solve within one second a problem using an algorithm that requires $f (n)$ bit operations, where each bit operation is carried out in $10^−9$ seconds, with $f (n) = n!$?

The number of bits carried out in $1$ second is $\frac{1}{10^{-9}}=10^9$.

We can estimate that using the fact that,

$$12! \lt 10^9 \lt 13!$$

Question 1: Is there a more systematic approach to solve it? I tried to replace $ n!$ with its upper bound $n^n$, but I am not sure if this is correct as the solution for $n!$ might be less than the solution of $n!$ upper bound $n^n$, or the upper bound solution of $n^n$ is acceptable answer for $n!$ based on question requirement?

$$n^n = 10^9$$

Avv
  • 1,159

1 Answers1

1

So first, if this were a "real-world" problem. Then the answer is 12 because $n$ should be an integer. (E.g. you can have a graph with 12 nodes, but not with 12.5 nodes.)

If we're trying to figure out for which real number $n$ do we have $n! = 10^9$ then we need to understand what that question even means because factorials are only defined for whole numbers. The most common extension of the factorial function to the reals (and complex numbers) is the Gamma function and we can use this (and a computer) to get an answer. The Gamma function is related to the factorial function by $\Gamma(n + 1) = n!$ when $n$ is a whole number.

So the question we want to ask our computer is: solve $\Gamma(n + 1) = 10^9$. But probably we should modify this to: solve $\log \Gamma(n + 1) = 9 \log 10$ since computers have good algorithms for computing $\log \Gamma(x)$ and $10^9$ is quite large so it might be harder to work with numbers at that scale.

If we do this, we get the answer $n \approx 12.2900691486\ldots$.

https://www.wolframalpha.com/input/?i=solve+loggamma%28n+%2B+1%29+%3D+9+log%2810%29

Addendum: so this method also gives a good way to compute the largest integer with $n! \le 10^9$ by rounding down. It's advantage is that if you have a computer algebra system with existing methods, you can program this in 1 line. E.g. in Mathematica, you could write

Floor[n] /. NSolve[{LogGamma[n + 1] == 9 Log[10] && n >= 0}, Reals]

But now let's say we don't have methods already for computing log-gamma or numeric solvers. Then probably the next best thing is to program (or work by hand) some sort of binary search:

  1. compute $10!, 20!, 30!, \ldots$ etc. until you have two values with $a! < 10^9 < b!$. In our case that would be $10! < 10^9 < 20!$. You can use a larger gap than $10$ if the number is really-really-really big.
  2. then just repeatedly divide the interval in two: $10! < 10^9 < 15!$
  3. $10! < 10^9 < 13!$
  4. $11! < 10^9 < 13!$
  5. $12! < 10^9 < 13!$

Binary search is generally quite fast. Here we have to compute only 6 factorials: 10, 20, 15, 13, 11, 12. If we did a linear search: 1!, 2!, 3!, ... it would take twice as long.

Trevor Gunn
  • 27,041