Questions tagged [factorial]
The factorial tag has no usage guidance.
17 questions
0
votes
1
answer
24
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
0
votes
1
answer
39
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
0
votes
1
answer
141
views
Time complexity of T(n) = 1600T(n/4) + n!
I'm trying to find the time complexity of T(n) = 1600T(n/4) + n! . So far I have thought of changing n! to something usable by the master theorem. Stirling's approximation gives us the equation
$$\...
- 1
0
votes
5
answers
322
views
Prove big O notation for $\log(n!)$ without applying Stirling's formula
I want to prove that,
$$ \log n! \in O(n \log n) \land \log n! \in \Omega(n \log n)$$
The straightforward approach is to apply Stirling's formula but I am looking for a different path to follow.
Can ...
0
votes
1
answer
2k
views
What is the most efficient algorithm for calculating factorials? [duplicate]
Calculating the factorial n! by the algorithm that defines it is of O(n) complexity because it requires n-1 multiplications to find the solution. Is there an algorithm that is any faster than that?
- 113
0
votes
0
answers
132
views
Fast factorial computation
I'm trying to solve this problem - https://codeforces.com/problemset/problem/711/E
I've already found and proved that the result is equal to:
$$
1 - \frac{2^n (2^n - 1) \cdots (2 ^ n - k + 1)}{2^{...
- 111
2
votes
2
answers
254
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)$.
...
- 155
-2
votes
2
answers
302
views
prove that log((n^2)!)= o(log((n!)^2))
i have a question - how i can prove that:
$\log((n^2)!) =\theta (log((n!)^2))$
i try something like that:
$\log((n^2)!) = 2*(log(n)!)=\theta(2*(log(n)!)=\theta(n\ log(n)) $
$\ \theta(log(n!)^2)=\...
2
votes
1
answer
468
views
Solving recurrence relation with minimum and factorial
I need to solve the following recurrence relation, where $T(n,m)$ is defined over $\Bbb N_+\times\Bbb N_+$.
$T(n,m)=\begin{cases}
1, & n=1\text{ or }m\leq 2(n-1)!\\
\min\limits_{a,b,c\geq 1,\ c\...
- 221
1
vote
1
answer
193
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:...
- 221
7
votes
1
answer
455
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!
- 221
0
votes
0
answers
52
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?
- 1
4
votes
1
answer
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
2
votes
0
answers
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
0
votes
1
answer
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 ...
- 131
1
vote
0
answers
579
views
How to get from factorial to a y-combinator?
In one of his conference talks Jim Weirich derives the applicative form of the y-combinator by refactoring a partial definition of factorial. The starting point in his talk is different than what ...
user22635
1
vote
1
answer
134
views
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 ...
- 2,019