patternMinor
Simplifying sum of falling factorials
Viewed 0 times
factorialsfallingsimplifyingsum
Problem
I wrote the worst algorithm in the world.
Doesn't matter what it does. I have just a question about folding formula for it's time complexity into some shorter form which would be easier to compute.
So I concluded that the equation for the number of operations is as follows:
$$n + n(n-1) + n(n-1)(n-2) + n(n-1)(n-2)(n-3) + \dots + n!\,.$$
Can we fold this sequence to some nice equation which will give us exact number of operations needed to complete this algorithm?
Doesn't matter what it does. I have just a question about folding formula for it's time complexity into some shorter form which would be easier to compute.
So I concluded that the equation for the number of operations is as follows:
$$n + n(n-1) + n(n-1)(n-2) + n(n-1)(n-2)(n-3) + \dots + n!\,.$$
Can we fold this sequence to some nice equation which will give us exact number of operations needed to complete this algorithm?
Solution
You gave the closed form for the number of operations:
$$
\sum_{m=1}^n n(n-1)\cdots(n-m+1) = \sum_{m=1}^n \frac{n!}{(n-m)!} = n! \sum_{m=0}^{n-1} \frac{1}{m!}.
$$
We can estimate this sum as follows:
$$
n! \sum_{m=0}^{n-1} \frac{1}{m!} =
n! \left(e - \sum_{m=n}^\infty \frac{1}{m!}\right) =
en! - 1 - \frac{1}{n+1} - \frac{1}{(n+1)(n+2)} - \cdots = \\
en! - 1 - O\left(\frac{1}{n}\right).
$$
$$
\sum_{m=1}^n n(n-1)\cdots(n-m+1) = \sum_{m=1}^n \frac{n!}{(n-m)!} = n! \sum_{m=0}^{n-1} \frac{1}{m!}.
$$
We can estimate this sum as follows:
$$
n! \sum_{m=0}^{n-1} \frac{1}{m!} =
n! \left(e - \sum_{m=n}^\infty \frac{1}{m!}\right) =
en! - 1 - \frac{1}{n+1} - \frac{1}{(n+1)(n+2)} - \cdots = \\
en! - 1 - O\left(\frac{1}{n}\right).
$$
Context
StackExchange Computer Science Q#86646, answer score: 4
Revisions (0)
No revisions yet.