CODEWITHSUNDEEP
algorithmbig-o
letsCode
letsCode

Reputation: 3046

Finding the best and worst O()

Using the following algorithm, im trying to determine the best and worst O().

minCoin(total, C[]) {
    if (total == 0) {return 0}
    min = MAX_VALUE
    for (i in C.length) {
        if (C[i] > total) {continue}
        value = minCoin(total - C[i], C)
        if (value < min) {min = value}
    }
    min = MAX_VALUE ? min : min++
    return min
}

Best: O(1) because if total == 0, well return Worst: O(nT) because n = the number of coins in the array, and T = the total we are making.

I also thought that the worst case could be O(2^n) where n is the number of recursive calls.

Is that correct?

Upvotes: 0

Views: 51

Answers (1)

mahbubcseju
mahbubcseju

Reputation: 2290

Currently the complexity is about O(2^n).So it is exponential .
But if you convert it to dynamic programming by memoization the complexity will be O(nT).

Solving by dynamic Programming :

memoization[total]={-1}// initially every index holds -1
minCoin(total, C[]) {
    if (total == 0) {return 0}

    if(memoization[total]!=-1) return memoization[total]; 
    min = MAX_VALUE
    for (i in C.length) {
        if (C[i] > total) {continue}
        value = minCoin(total - C[i], C)
        if (value < min) {min = value}
    }
    min = MAX_VALUE ? min : min++
    return memoization[total]=min 
}

once we calculated for total we change the value of memoization of total from -1 to its result . So if we get total again we will just return memoization[total] as we stored the result on it before.

For details about DP: https://www.geeksforgeeks.org/dynamic-programming/

Upvotes: 2

Related Questions