/* This of course assumes that there are no coins which are not integer values,
 * and that an array of coins A exists which is length m and is 
 * indexed A[1..m]. The coin at A[1] = 1 by definition, and A[k] <= A[k + 1].
 */
int coins(int nAmount, int nCoinIndex)
{
   if(nAmount == 0) return 0;
   else if((nCoinIndex < 1) ||
           (nAmount < 0))
   {  /* Need to have some representation for INFINITY.  It could simply
       * be the coint amount + 1.
       */
      return INFINITY;
   }
   else
   {
      return min(coins(nAmount - A[nCoinIndex], nCoinIndex) + 1,
                 coins(nAmount, nCoinIndex - 1));
   }
}
Consider T(n).

Oh my goodness! We have double recursion going on here. We have a stop state for nAmount, as well as one for nCoinIndex.

Aren't you glad I am not giving this for the midterm! :-)

T(n,m)

Minimize constants, the if decision statement and the end of the recursion can be time c1. The else will be the tricky part.

Here we see a call to min that has two recursive calls. Hence, both calls will be made to determine which is the minimum.

I will call nAmount n, and note that n is the variable we are doing the recursion on (discuss). Nope, not true. The second call in the minimum is doing a recursive call on the same function but with a different variable nCoinIndex (I will call m)

T(n,m) = c1 for n < 0, m<1
For m>1, n > 0, let us consider a worse case with one coin of value 1, we see
T(n,m) = T(n-1,m) + T(n, m-1)

Now, note that this worse case for coin value is the best situation for the second recursive call - since we then see m-1=0 and hence this call would stop.

So we really see that in the first call it is significant that we consider the amount A(m) (or more specifically A(i) as m decreases).
T(n,m) = T(n-A(m),m) + T(n, m-1)

Well, more thought on this one...Here perhaps we would consider an average case rather than a best and worse - where average would be a function of the values of A(i) and A's size.