title: Analyzing the time complexity of Coin changing
body: <p>We're doing the classic problem of determining the number of ways that we can make change that amounts to Z given a set of coins.</p>
  
  <p>For example, Amount=5 and Coins={1, 2, 3}. One way we can make 5 is {2, 3}.</p>
  
  <p>The naive recursive solution has a time complexity of factorial time.</p>
  
  <blockquote>
    <p>f(n) = n * f(n-1) = n!</p>
  </blockquote>
  
  <p>My professor argued that it actually has a time complexity of <code>O(2^n)</code>, because we only choose to use a coin or not. That intuitively makes sense. However how come my recurence doesn't work out to be <code>O(2^n)</code>?</p>
  
  <p><strong>EDIT:</strong></p>
  
  <p>My recurrence is as follows:</p>
  
  <pre><code>   f(5, {1, 2, 3})
       /           \                     .....
  f(4, {2, 3})  f(3, {1, 3})        .....
  </code></pre>
  
  <p>Notice how the branching factor decreases by 1 at every step.</p>
  
  <p>Formally.</p>
  
  <blockquote>
    <p>T(n) = n*F(n-1) = n!</p>
  </blockquote>