Mathematically calculate the time complexity of all permutations of a string
I am trying to mathematically analyze the complexity of the following code
void perm(String str){ perm(str, "");
}
void perm(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); perm(rem, prefix + str.charAt(i)); } }
}I saw this website that explains the complexity using common sense but I want to try and solve this mathematically.
the equations I got are
(1) $T(n) = n(n+T(n-1)) = n^2 + nT(n-1)$
(2) $T(n) = n^2 + n(n-1)^2 + n(n-1)(n-2)^2 + ... = \frac{nn!}{(n-1)!} + \frac{(n-1)n!}{(n-2)!} + \frac{(n-2)n!}{(n-3)!} + ... $
(3) $T(n) = n!(\frac{n}{(n-1)!} + \frac{n-1}{(n-2)!} + \frac{n-2}{(n-3)!} + ... + \frac{1}{0!})$
now I am stuck as I can't seem to find the value of the sum..
was the calculations right? got any tips for finding the value of $(\frac{n}{(n-1)!} + \frac{n-1}{(n-2)!} + \frac{n-2}{(n-3)!} + ... + \frac{1}{0!})$ ?
Thanks
$\endgroup$ 11 Answer
$\begingroup$\begin{eqnarray*} \sum_{k=1}^n\frac k{(k-1)!}x^k &\simeq& \sum_{k=1}^\infty\frac k{(k-1)!}x^k \\ &=&\left(x\frac{\mathrm d}{\mathrm dx}\right)^2 \sum_{k=1}^\infty\frac{x^k}{k!} \\ &=& \left(x\frac{\mathrm d}{\mathrm dx}\right)^2\left(\mathrm e^x-1\right) \\ &=&\left(x^2+x\right)\mathrm e^x\;. \end{eqnarray*}
Evaluating at $x=1$ yields $2\mathrm e$ as an estimate of your sum for large $n$.
$\endgroup$ 3
