title: Shouldn't the space complexity of insertion sort be O(N)?
body: <p>This covers a "software algorithm" from <a href="https://stackoverflow.com/help/on-topic">https://stackoverflow.com/help/on-topic</a></p>
  
  <p>This is a from a lecture slide from class 
  <img src="https://i.stack.imgur.com/LD0Ld.png" alt="enter image description here"></p>
  
  <p>Here is the implementation of insertion sort that we used </p>
  
  <pre><code>public static void insertionSort(int[] a) {
       for (int i = 1; i &lt; a.length; i++) {
            int temp = a[i];
            int j = i;
            while (j &gt;= 1 &amp;&amp; a[j - 1] &gt; temp) {
                  a[j] = a[j - 1];
           }
           a[j] = temp;
       }
  }
  </code></pre>
  
  <p>I would agree that the space complexity of local variables would be O(1) because its just the same local variables each time no matter the input size, i, j, and temp will each take up a block of memory. </p>
  
  <p>However I am confused about the space complexity of the array. <a href="http://www.cs.northwestern.edu/academics/courses/311/html/space-complexity.html" rel="nofollow noreferrer">http://www.cs.northwestern.edu/academics/courses/311/html/space-complexity.html</a> had a similar example,</p>
  
  <pre><code>int sum(int a[], int n) {
      int r = 0;
      for (int i = 0; i &lt; n; ++i) {
         r += a[i];
      }
      return r;
  }
  </code></pre>
  
  <p>and said that this algorithm would require N units of memory for a, meaning its space complexity is O(N)?</p>
  
  <p>Which is it? O(N) because the array would require N units of memory(dependent on input size) or O(1) because of pass by reference?</p>