Coin Change analysis

Question

{1,3,5} denomination coins; Sum = 11. find minimum number of coins which can be used to make the sum (We can use any number of coins of each denomination)

I searched for Run Time complexity of this Coin change problem particularly using dynamic programming method. But was not able to find explanation anywhere.

How to calculate the complexity of non dynamic solution and then change it for the dynamic one? (not the greedy one)

Edit:

Here is an implementation for which analysis was asked.

public int findCoinChange(int[] coins, int sum,int count) {

    int ret = 0, maxRet = -1;
    if(sum ==0)maxRet = count;
    else if(sum < 0)maxRet = -1;
    else{
        for(int i:coins){
            ret = findCoinChange(coins, sum - i,count+1);
            if(maxRet< 0)maxRet = ret;
            else if(ret >=0 && ret < maxRet){
                    maxRet = ret;
                }
            }
    }
    if(maxRet < 0)return -1;
    else return maxRet;
}

Looks like Combinatorial explosion to me. However I am not sure how to deduce a run time complexity for this.

Answer 1

The dynamic programming solution to this problem is clearly O(k * n) (nested loops, blah blah blah) where k is the number of coins and n is the amount of money that change is being made for.

I don't know what you mean by non-dynamic programming solution. Sorry, you're going to have specify what algorithm you mean. The greedy algorithm fails in some cases, so you shouldn't be referring to that. Do you mean the linear programming solution? That's a terrible approach to this problem because we don't know what the complexity is, and it's possible to make it run arbitrarily slowly.

I also don't know what you mean by "change it for the dynamic one."