title: Time complexity of this combination algorithms
body: <p>I was implementing a combinations algorithm. This should generate unique combinations of length from the given list .</p>
  
  <p>For example:</p>
  
  <pre><code>Input list [1, 2, 3, 4, 5] with k = 3
  should generate output
  
      [1, 2, 3]
      [1, 2, 4]
      [1, 2, 5]
      [1, 3, 4]
      [1, 3, 5]
      [1, 4, 5]
      [2, 3, 4]
      [2, 3, 5]
      [2, 4, 5]
      [3, 4, 5]
  </code></pre>
  
  <p>The working python code is given below for reference.</p>
  
  <pre><code>def my_combinations(items, k, out):
      if k==0:
          print out
          return
  
      for i in range(len(items)):
          new_out = out[:]
          new_out.append(items[i])
          my_combinations(items[i+1:], k-1, new_out)
  </code></pre>
  
  <p><strong>Question:</strong></p>
  
  <p>What is the time complexity of this algorithm?</p>
  
  <p>I started with the recurrence equation.</p>
  
  <pre><code>Base case: T(n, 0) = 1
  Recurion : T(n, k) = T(n-1, k-1) + T(n-2, k-1) + T(n-3, k-1) + .. + T(0, k-1) + 1
                     = n * T(n-1, k-1) + 1
  </code></pre>
  
  <p>T(n) = ???</p>
  
  <p>solution by expansion.</p>
  
  <p>This question is different from the <a href="https://stackoverflow.com/questions/31120402/complexity-when-generating-all-combinations">Complexity when generating all combinations</a>. </p>
  
  <p>My question is about the time complexity of the given implementation and the link question talks about runtime of generating all combinations in general.</p>