Time Complexity - Bad Recursion - British Change Combinations

Question

I recently came up with a naive (+ poor) solution to the British Change Problem (i.e. how many combinations of coins can generate a given total). I have a better solution now, but was still interested in solving the time and space complexity of the two solutions below.

Worst Solution

This solution recursively tries combining every number against itself and every other number, resulting in a lot of duplicate work. I believe it's O(n^n) time and not sure how to measure space complexity (but it's huge, since we're storing every result). Thoughts?

var makeChange = function(total){ // in pence
  var allSets = new Set();
  var coins = [1,2,5,10,20,50,100,200];

  var subroutine = (arr, total) => {
    if(total < 0){ return; }
    if(total === 0){
      allSets.add(''+arr);
    } else {
      // increase each coin amount by one and decrease the recursive total by one
      for(var i = 0; i<coins.length; i++){
        if((total - coins[i]) >= 0){
          subroutine(arr.slice(0,i).concat(arr[i]+1).concat(arr.slice(i+1)), (total - coins[i]))
        }
      }
    }
  };

  var zeros = new Array(coins.length).fill(0);
  subroutine(zeros, total);
  return allSets.size;
};

Improved Solution

This solution still has massive space complexity but I believe the time complexity has -improved- to O(n!) since we're recursing on smaller subsets of coins each time.

var makeChange = function(total){ // in pence
  var allSets = new Set();
  var coins = [1,2,5,10,20,50,100,200];

  var subroutine = (arr, total, start) => {
    if(total < 0){ return; }
    if(total === 0){
      console.log(''+arr);
      allSets.add(''+arr);
    } else {
      // only solve for coins above start, since lower coins already solved
      for(var i = start; i<coins.length; i++){
        if((total - coins[i]) >= 0){
          subroutine(arr.slice(0,i).concat(arr[i]+1).concat(arr.slice(i+1)), (total - coins[i]), i);
        }
      }
    }
  };

  var zeros = new Array(coins.length).fill(0);
  for(let i = 0; i<coins.length; i++){
    subroutine(zeros, total, i);
  }

  return allSets.size;
};

Please help me to understand if my time/space complexity estimates are correct, and how to better estimate future problems like these. Thanks!

This can be achieved in O(n^2) time by the use of DP ... you should read on algorithms more to implement this using DP — zenwraight, Jun 08 '17 at 19:52
I'm not interested in improving the algorithm, just in understanding how to calculate recursive time complexity. — colorbynumber, Jun 09 '17 at 16:15

Jayson Boubin · Accepted Answer · 2017-06-09T18:02:56.990

The complexity of the first algorithm is not actually an O(n^n). N is a variable which represents your input. In this case, I will refer to the variable "total" as your input, so N is based on total. For your algorithm to be O(n^n), it's recurrence tree would have to have a depth of N and a branching factor of N. Here, your depth of your recurrence is based on the smallest variable in your coins array. There is one branch of your recursion tree where you simply subtract that value off every time and recurse until total is zero. Given that that value is constant, it is safe to say your depth is n. Your branching factor for your recursion tree is also based off of your coins array, or the number of values in it. For every function call, you generate C other function calls, where C is the size of your coins array. That means your function is actually O(n^c) not O(n^n). Your time and space complexities are both based off of the size of your coins array as well as your input number.

The space complexity for your function is O(n^c * c). Every time you call your function, you also pass it an array of a size based on your input. We already showed that there are O(n^c) calls, and each call incorporates an array of size c.

Remember when analyzing the complexity of functions to take into account all inputs.

Thanks for the explanation on the N depth. For the space complexity, the array is a constant size of C, rather than N. So would this be O(c*n^c)? — colorbynumber, Jun 09 '17 at 16:14
@colorbynumber Yeah, you're right. I thought you were passing around your output arrays for some reason, but they're going into your set. Of course, your set's size is insignificant compared to the arrays created per call, so they're the source of your space complexity. — Jayson Boubin, Jun 09 '17 at 18:04

Time Complexity - Bad Recursion - British Change Combinations

1 Answers1