I have problem. I've calculated memory complexity of my algorithm. In exchange of very good time complexity of my algorithm, I have memory complexity $x!$, where $x$ is number of elements my algorithm gets.
Number of numbers I can easily store equals $2^{22000000}$. How many elements can my algorithm accept?
$x!=2^{22000000}$
How can I solve it? I've tried several calculators (even wolfram alpha), but no calculator was able to solve it. I've tried to use Stirling approximation ( Solving equations with factorials? ), but the number is just too big.
Do you know some online calculator that would be powerfull enough to calculate it? Or some other method to calculate it? I do not need exact number, I just want to know how big the number is (if I could tell number of digits in the number, it would be great).
Thanks, Peter
Best Answer
In this answer is given the approximation $$ n\sim e\exp\left(\operatorname{W}\left(\frac1{e}\log\left(\frac{n!}{\sqrt{2\pi}}\right)\right)\right)-\frac12 $$ Plugging in $n!=2^{22000000}$, we get $n\approx1175108.4$. Then $$ 1175108!\approx2^{21999991.937} $$ and $$ 1175109!\approx2^{22000012.101} $$