# Questions tagged [factorial]

The tag has no usage guidance.

17 questions
Filter by
Sorted by
Tagged with
14 views

### Calculating nth permutation without repetition efficiently, with variable number of elements

I know I can use the factorial number system to calculate ordered permutations of a set efficiently, given a constant length (for example, ...
• 141
38 views

### Which one grows faster, an exponential function where the exponent grows faster than logarithmic or a factorial powered by n?

Which function grows faster: $$f(n) = 4^{n^2 \log_2 n} \text{ or } g(n) = (n!)^n$$ Which is true? $f(n) = O(g(n))$ $g(n) = O(f(n))$ i.e., $f(n) = \Theta(g(n))$ none of the above? For lower values of ...
• 1
140 views

• 111
249 views

### Efficient way to reduce a binomial coefficient as a fraction

Here is the full problem. You need to calculate Euler's totient function of a binomial coefficient $C_n^k$. Input The first line contains two integers: $n$ and $k$ $(0 \le k \le n \le 500000)$. ...
278 views

• 231
1 vote
188 views

### Recurrence with Minimum

I need to solve the following recurrece: $T(n,m)=\begin{cases} 1, & m\leq 2(n-1)!\\ \min\limits_{a,b\geq 1\\a\cdot b\leq (n-1)!}{T(n-1,a)+T(n-1,b)+T(n,m-ab)}, & \text{else} \end{cases}$ Note:...
• 231
454 views

### Asymptotics question

Is $\frac {n!} {2!\cdot 4!\cdot 8!\dots (n/2)!}=O(4^n)$? I am really stuck and I tend to believe it's true, but I don't know how to prove it. Any help would be appreciated!
• 231
50 views

### Where f(n) = n! belongs to? P, co-P, NPComplete or NPHard? [duplicate]

Where f(n) = n! belongs to? P, co-P, NPComplete or NPHard?
2k views

### Why is the complexity of factorial a function of n?

When we compute the complexity of calculating factorial of a number $n$ why is it in terms of $n$ instead of the number of the number of bits occupied by the number of bits occupied by $n$ (like we do ...
• 237
2k views

### Can factorial be done in O(1) and proof?

The typical way to compute the factorial would take $O(n)$ because it calls itself recursively. However, there are many other ways to compute the factorial function based off the gamma function, ...
• 121
2k views

### Complexity calculation using a recurrence relation [duplicate]

I just can't solve this problem, I'm new to reccurences. I have this recurrence $T(n)=n*T(n-1)$ $T(1)=1$ The second term will be: $T(n-1)=(n-1)*T(n-2)$ And so on. It's complexity is O(n!) but i ...
• 31
1 vote
### Generating all factorials up to $n$: faster than naive approach?
I'm aware of prime decomposition and parallel approaches to calculating one factorial; however, if I want the factorials of all numbers up to $n$, is there anything more efficient than the naive ...