0

I implemented symmetric groups via factorial number system (or "factoriadic"): 1 2

So I tried to calculate the complexity. Since the unit of complexity is bits, I calculated how many bits compose a number of factoriadic. Given that it has radix $N$, it has $\log 1 + \log 2 + \cdots + \log N = \log N!$ bits. We set this as $n$, and represent all complexities as a function of $n$. Is this the correct way to analyze time complexity?

Now given a complexity is $f(N)$, we need the inverse function of $\log N!$. What is it?

Dannyu NDos
  • 2,029

1 Answers1

1

I don't know of an easily expressed inverse. You can use Stirling's approximation $$N! \approx N^Ne^{-N}\sqrt{2\pi N}\\ \log N! \approx (N +\frac 12)\log N -N+\frac 12\log(2\pi)$$ and do one dimensional root finding to get $N$ from $\log N!$ This uses natural logs rather than base $2$ logs, but it is a small correction.

Ross Millikan
  • 374,822
  • Sorry for making confusions. I'm not familiar with LaTeX. I mean $\log N! \approx N \log N$. – Dannyu NDos Aug 22 '19 at 11:16
  • That approximation ignores the $-N$ . It maybe accurate enough for the purpose at hand. For $N=50$ we have $\log(50!) \approx 148.48, 50\log (50)\approx 195.60$ – Ross Millikan Aug 22 '19 at 15:11