title: Python list.clear() time and space complexity?
body: <p>I am writing a blogpost on Python <code>list.clear()</code> method where I also want to mention about the time and space complexity of the underlying algorithm. I expected the time complexity to be <strong>O(N)</strong>, iterate over the elements and free the memory? But, I found an <a href="https://www.ics.uci.edu/%7Ebrgallar/week8_2.html" rel="nofollow noreferrer">article</a> where it is mentioned that it is actually an <strong>O(1)</strong> operation. Then, I searched the source code of the method in CPython implementation and found a method which I believe is the actual internal implementation of <code>list.clear()</code>, however, I am not really sure it is. Here's the source code of the method:</p>
  <pre class="lang-c prettyprint-override"><code>static int
  _list_clear(PyListObject *a)
  {
      Py_ssize_t i;
      PyObject **item = a-&gt;ob_item;
      if (item != NULL) {
          /* Because XDECREF can recursively invoke operations on
            this list, we make it empty first. */
          i = Py_SIZE(a);
          Py_SIZE(a) = 0;
          a-&gt;ob_item = NULL;
          a-&gt;allocated = 0;
          while (--i &gt;= 0) {
             Py_XDECREF(item[i]);
          }
          PyMem_FREE(item);
      }
      /* Never fails; the return value can be ignored.
         Note that there is no guarantee that the list is actually empty
         at this point, because XDECREF may have populated it again! */
      return 0;
  }
  </code></pre>
  <p>I could be wrong but it does look like <strong>O(N)</strong> to me. Also, I found a similar question <a href="https://stackoverflow.com/questions/46985483/python-list-clear-complexity">here</a>, but there's no clear answer there. Just want to confirm the actual <strong>time and space complexity</strong> of <code>list.clear()</code>, and maybe a little explanation supporting the answer. Any help appreciated. Thanks.</p>