Questions tagged [factorial]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
34 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 ...
Kong's user avatar
  • 1
0 votes
1 answer
139 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 $$\...
sonu786's user avatar
0 votes
5 answers
261 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 ...
prideandprejudice's user avatar
0 votes
1 answer
1k 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?
magnetlion's user avatar
0 votes
0 answers
127 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^{...
yomol777's user avatar
  • 111
2 votes
2 answers
242 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)$. ...
Levon Minasian's user avatar
-2 votes
2 answers
271 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)=\...
גיא בוהדנה's user avatar
2 votes
1 answer
459 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\...
Dudi Frid's user avatar
  • 161
1 vote
1 answer
187 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:...
Dudi Frid's user avatar
  • 161
7 votes
1 answer
451 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!
Dudi Frid's user avatar
  • 161
0 votes
0 answers
44 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?
Misterio's user avatar
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 ...
Faustus's user avatar
  • 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, ...
mtheorylord's user avatar
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 ...
Ruben P's user avatar
  • 31
1 vote
0 answers
546 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 ...
user avatar
1 vote
1 answer
121 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 ...
G. Bach's user avatar
  • 2,019