CODEWITHSUNDEEP
algorithmbig-o
dead programmer
dead programmer

Reputation: 4373

Algorithm analysis for below function

I have made a solution of chaining coin problem using recursion. I want to know to calculate the big oh complexity for this solution.

int chainingCoinRec(int val[], int p){
        int min=Integer.MAX_VALUE;


        if(p==0){
            return 0;
        }

        int i=0;
        while( i<val.length && val[i]<=p ){
            int temp=chainingCoinRec(val, p-val[i])+1;
            if(temp<min)
                min=temp;
                i++;
        }
        return min;
    }

Upvotes: 0

Views: 60

Answers (1)

Henry
Henry

Reputation: 43798

At each recursion level you have a loop with at most val.length iterations; lets call this l.

The recursion depth is at most p divided by the smallest element in val lets call this quantity e.

This means we have e nested loops, each running over l iterations.

The total effort is therefore O(le).

Also note, that you are doing much more work here than necessary to solve the problem. You enumerate solutions that are basically equivalent because they only differ in the order of the coins.

Upvotes: 2

Related Questions