How does my professor come up with the recursive case in this algorithm analysis?

Question

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.

Answer 1

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.

Answer 2

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$.