title: Time Complexity - Bad Recursion - British Change Combinations
body: <p>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 href="https://stackoverflow.com/a/36373256/8133220">a better solution</a> now, but was still interested in solving the time and space complexity of the two solutions below.</p>
  
  <p><strong>Worst Solution</strong></p>
  
  <p>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?</p>
  
  <pre><code>var makeChange = function(total){ // in pence
    var allSets = new Set();
    var coins = [1,2,5,10,20,50,100,200];
  
    var subroutine = (arr, total) =&gt; {
      if(total &lt; 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&lt;coins.length; i++){
          if((total - coins[i]) &gt;= 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;
  };
  </code></pre>
  
  <p><strong>Improved Solution</strong></p>
  
  <p>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.</p>
  
  <pre><code>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) =&gt; {
      if(total &lt; 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&lt;coins.length; i++){
          if((total - coins[i]) &gt;= 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&lt;coins.length; i++){
      subroutine(zeros, total, i);
    }
  
    return allSets.size;
  };
  </code></pre>
  
  <p>Please help me to understand if my time/space complexity estimates are correct, and how to better estimate future problems like these. Thanks!</p>