title: Time complexity of scipy.null_space()
body: <p>I have the following snippet of code:</p>
  <pre><code>(... some previous code ...)
  
  vecs = np.array(vecs_list, dtype=int)
  
  kernel = scipy.linalg.null_space(np.transpose(vecs))
  rows, columns = kernel.shape
  
  (... some ensuing code ...)
  </code></pre>
  <p>Let me clarify some things:</p>
  <ul>
  <li><code>vecs_list</code> : is a list of <em>L</em> lists each with size <em>s</em>. I like to think of it as an <em>L</em>x<em>s</em> matrix.</li>
  <li>there <strong>is</strong> a reason as to why I start with a list and then make the conversion to a np.array (this relates to the nature of the prior code, but the object that we start from really must be a list of lists!).</li>
  </ul>
  <p>My question is the following: what is the time complexity of this snippet of code as it stands?</p>
  <hr />
  <p>The way I see it the answer goes something like this:</p>
  <ul>
  <li><code>vecs = np.array(vecs_list, dtype=int)</code> : might take <em>O(s</em>**L)* time</li>
  <li><code>np.transpose(vecs)</code> : <em>O(1)</em> time</li>
  <li><code>scipy.linalg.null_space(*)</code> : uses SVD but I am not entirely certain what that means for the time complexity. I suppose I would expect <em>O(n^3)</em> for an <em>n</em>x<em>n</em> matrix but here the matrix is not a square matrix and I am not sure of the implications. Do you know what is the time complexity of this method? Is there a better alternative from the big-<em>O</em> point of view?</li>
  <li><code>kernel.shape</code> : <em>O(1)</em> time</li>
  </ul>
  <hr />
  <p>Thank you in advance.</p>
  <hr />
  <p><strong>EDIT:</strong> After some quick studies where I varied <em>s</em> and <em>L</em> separately, I got the following graphs:
  <a href="https://i.stack.imgur.com/yB0P5.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/yB0P5.png" alt="enter image description here" /></a></p>
  <p><a href="https://i.stack.imgur.com/G1vYF.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/G1vYF.png" alt="enter image description here" /></a></p>
  <p>which seems to suggest that <em>O(s^2 L^2)</em>. This is a bit disturbing because it indicated that if <em>s=L</em> then <em>O(s^4)</em> instead of the <em>O(s^3)</em> that one would expect. Any thoughts about this?
  Thank you!</p>