CODEWITHSUNDEEP
javaalgorithmtime-complexity
committedandroider
committedandroider

Reputation: 9261

How to show that the time complexity of algorithm is O(2^n)?

I'am doing a practice interview question from HackerRank Coin Change

I got stuck and I'm trying to understand a Solution to this problem. Here is the recursive solution to this problem.(with my comments to understand it)

  public static int numWays(int[] coins, int sumTo) {
   return numWaysWhichCoin(coins, sumTo, 0);
}
private static int numWaysWhichCoin(int[] coins, int sumTo, int whichCoin) {
    if(sumTo == 0) {
        //empty set
        return 1;
    } else if(sumTo < 0) {
        //no way to form a negative sum with positive coin values
        return 0;
    }  else {
        //sumTo is positive 
        //case gone through all the coins but still a positive sum. Impossible
        if(sumTo > 0 && whichCoin == coins.length) {
            return 0;
        }
        //with and without. With, you can keep using the same coin 
        return numWaysWhichCoin(coins, sumTo - coins[whichCoin], whichCoin) + numWaysWhichCoin(coins, sumTo, whichCoin + 1);
    }
}

The author states that the algorithm runs in O(2n) time complexity. From my experience in interviews, you are expected to justify your answers.

How wold you justify this time complexity? From my previous work to showing algorithms run in O(2n) time, I would use recurrence relations, like(Fibonacci) T(n) = T(n-1) + T(n-2) +c <= 2T(n-1) + c,
T(1) = d, but I can't derive a recurrence relation like that from here. Is there another way of going about this justification?

Upvotes: 4

Views: 314

Answers (2)

gen-y-s
gen-y-s

Reputation: 881

Suppose there are R different combinations (the requested result). The number of coins of the i-th coin (0<=i<=M-1) used in a specific solution r (0<=r<=R-1) is C(i, r). So for each r in 0...R-1 we have C(0,r)+C(1,r)+....C(M-1,r)=N. The maximum value of C(i, r) for each r in 0...R-1 is max_c(i)=floor(N/Vi) (Vi is the value of coin i), which less or equal to N. The sum of c_max(i) where i=0..M-1 is <= N*M. So the total number of individual coins used in all the combinations is O(NM). The algorithm you presented simply iterates all the sub-groups of the group above of c_max(i) individual coins for each coin value Vi, which O(2^(NM)).

Upvotes: 1

sivi
sivi

Reputation: 11114

The two recursive calls make it act like a binaric tree that grows in 2 n rate.

Your algorithm as far as complexity is identical to Fibonacci recursive algorithem. So you can look and find the many answers and explenations and even proofs why recursive Fibonacci is from the order of 2 n.

Upvotes: 1

Related Questions