What is the time complexity of this permutation algorithm?

Question

The algorithm is as follows:

void permutation(String str) {
     permutation(str, "");
}

void permutation(String str, String prefix) {
    if ( st r.length() == e) {
         System.out.println(prefix);
    } else {
       for (int i = j; i < str.length(); i++) {
           String rem = str.substring(e, i) + str.substring ( i + 1);
           permutation(rem, prefix + str.charAt(i));
       }
   }
}

Computing the total number of function calls for input size n, we have

$$\sum_{i=0}^n n!/i! = e (n! - Γ(n + 1) + Γ(n + 1, 1)) $$

So we end up with: $$ O(e (n! - Γ(n + 1) + Γ(n + 1, 1))) $$ $$ O(n! - Γ(n + 1) + Γ(n + 1, 1)) $$

What I would like to know is how I can simplify this further?

Answer 1

I would approach it like this: $$ A_n=\sum_{i=0}^n n!/i! = n!\left(\sum_{i=0}^{\infty} 1/i! - \sum_{i=n+1}^{\infty} 1/i!\right). $$ Neglecting the subtrahend and using the exponential series we get an upper bound: $$ A_n\leq n!\left(e^1 -0\right)=n!\cdot e. $$ Again we use the exponential series and some estimates for a lower bound: $$ A_n\geq n!\left(e^1 - \sum_{i=0}^{\infty} 1/(i!\cdot (n+1)!)\right)= $$ $$ n!\left(e - \frac{1}{(n+1)!}\sum_{i=0}^{\infty} 1/i!\right)= n!\left(e - \frac{1}{(n+1)!}\cdot e\right)= $$ $$ n!\cdot e-\frac{n!}{(n+1)!}\cdot e\geq n!\cdot e-e. $$ Upper and lower bound essentially match and Sterling's formula yields: $$ A_n\sim e\sqrt{2\pi n}\left(\frac{n}{e}\right)^n. $$