Asymptotic complexity of generating permutation

Question

I stumbled on this question while answering a question on stackoverflow. A guy asked what the complexity of the following code was.

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

We should first notice that each call to String rem=str.substring(0,i)+str.substring(i+1) costs $O(n)$. If we denote with $T(n)$ the cost of a call to permutation with an input of size $n$ then $$T(n) = n [n + T(n-1)]$$

because the cost of the body of the for in the else path is $n+T(n-1)$ in the else path.

• What is (if one exists) a method for solving T(n)?

I have tried to expand $T(n)$ : $$T(n) = n^2 + n(T(n-1) $$ $$= n^2 + n( (n-1)^2 + (n-1)T(n-2)) $$ $$= n^2 + n( (n-1)^2 + (n-1)[(n-2)^2+(n-2)T(n-3)])$$ $$=n^2 + n( (n-1)^2 + (n-1)(n-2)^2+(n-1)(n-2)T(n-3)])$$ $$=n^2 + n(n-1)^2 + n(n-1)(n-2)^2+n(n-1)(n-2)T(n-3)]) \ldots n!$$

which should be to $$ T(n) = \sum_{k=0}^{n-1}\frac{n!(n-k)}{(n-k-1)!} $$

• This is where I am stuck. What is the value of that summation?

Since I was stuck I have tried to get an upper bound on $T(n)$ reasoning as follows:

I know that there are $n!$ permutation and that in the recursion tree each of them is a leaf. For each leaf there is a path to the root of exactly length $n$. As an upper bound it is safe to assume that there are not more than $n*n!$ nodes in the tree (no path from leaf to root share a node). I know that node costs $O(n)$ cause of the substring call so the overall complexity is $O(n^2n!)$

• Is this approximation correct?

Answer 1

Rewriting your sum as $$n!\sum_{\ell=1}^n \frac{\ell}{(\ell-1)!}$$ you get from keeping the first term that $T(n)\geq n!\cdot 1$, and by majoring by $$n!\sum_{\ell=1}^\infty \frac{\ell}{(\ell-1)!}=n!\sum_{\ell=0}^\infty \frac{(\ell+1)}{\ell!} = 2e n!$$ that $T(n) \leq 2e n!$. So $T(n) = \Theta(n!)$.