title: Laplace Expansion complexity calculation (recursion)
body: <p>Hey im having trouble calculating the complexity of <a href="http://i.stack.imgur.com/Lm1fO.png" rel="nofollow">Laplace Expansion</a> using my code:</p>
  
  <pre><code>def determinant_laplace(self, i=0):
      assert self.dim()[0] == self.dim()[1]
      if self.dim() == (1,1):
          return self[0,0]
      else:
          det = 0
          for col in range(self.dim()[1]):
              det += ((-1)**(col+i) *self[i,col]* self.minor(i,col).determinant_laplace())
          return det
  </code></pre>
  
  <p>to better undestand this here is how a minor is calculated (in my code):</p>
  
  <pre><code>def minor(self, i, j):
      t = self.dim()[0] # rows
      k = self.dim()[1] # columns
      assert isinstance(i, int) and isinstance(j, int) \
      and i &lt; t and j &lt; k
      newMat = Matrix(t-1,k-1) # new matrix will be with 1 less col and row
      for row in range(t):
          for col in range(k):
              if row &lt; i and col &lt; j:
                  newMat[row,col] = self[row,col]
              elif row &lt; i and col &gt; j:
                  newMat[row,col-1] = self[row,col]
  
              elif row &gt; i and col &lt; j:
                  newMat[row-1,col] = self[row,col]
  
              elif row &gt; i and col &gt; j:
                  newMat[row-1,col-1] = self[row,col]
      return newMat
  </code></pre>
  
  <p>as you can see, the complexity of creating a minor in nxn matrix is O(n^2).</p>
  
  <p>so i'm torn by the overall complexity is it O(n!) or O((n+1)!) or O((n+2)!) ?</p>
  
  <p>Why it's O(n!) : Wikipedia says so, but I guess their implementation is different and maybe they neglect some calculating regarding the minor.</p>
  
  <p><strong>Why it's O((n+1))! : The recursion sequence is n(n^2 + next(recursion_minor)..) = O(n*n!) = O((n+1)!)</strong></p>
  
  <p>Why it's O((n+2)!) : calculating a minor is O(n^2) and we calculate n! of those so we get O(n^2)*O(n!)=O(n+2)!</p>
  
  <p>Personnaly I lean towards the <strong>Bold</strong> statement.</p>
  
  <p>Thanks for your help.</p>