How does my professor come up with the recursive case in this algorithm analysis? My professor gave us the following explanation for the recursive algorithm for finding the permutations of a set of numbers:



When he has (T(m+1), n-1)) where does that come from? Why is it m+1 and n-1? I'm really confused as to where that comes from.
 A: The $m+1$ arises in two different ways as described that happen to have the same value:  to pass arguments to each call, it concatenates P to i (the cost is m+1), ... and $P$ is the set of elements that have been printed, which will have size $m+1$ on iteration $m+2$ in the call to $T(m+1,n-1).$
Because $P$ is a "recursive array of the numbers already printed out," the code must add to $P$ the current item being printed as or after it has been printed.  The cost of this addition is claimed to be $m+1,$ which is presumably a proven result or else a defined condition.  The size of $P$ after this addition also happens to be $m+1$.  This applies to both the "degenerate" case where $S$ has one element and to the recursive case, which is why the term $m+1$ occurs in both formulas.
The $n-1$ term comes from removing an element from the set $S$ as or after it has been printed, so that $S$ has one less term after each iteration of the loop.
A: The context is calling $\textrm{printperm}((P,i), S-\{i\})$ recursively from $\textrm{printperm}(P, S)$. The cost of that recursive call is $T(|(P,i)|, |S-\{i\}|)$.
$|(P,i)| = |P| + 1 = m+1$ by definition of $m$.
$|S-\{i\}| = |S| - 1 = n-1$ by definition of $n$.
