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

As he said, m represents the current size of P and n represents the size of S, in each recursive call you remove a number from S and add it to P, thus the size of your current permutation is increased by 1 (m+1) and the number of available numbers to add to the permutation is decreased by 1 (n-1)

Note that it is multiplied by n as you perform this action for each number in S.

Answer 2

Note that part that says:

Let m be the length of P and n be the size of S

And then in printperm(P, S), you're calling printperm((P,i), S-{i}).

So, when recursing, we will add one element to P, and remove on element from S.

Thus m will increase by one and n will decrease by one, thus we get T(m+1, n-1)

I hope that helps.