title: Append in Python not in O(1)
body: <p>I'm trying to monitor complexity in Python's lists. So I wrote the script above thinking I would have a O(1) complexity for inserting an item et the end and a O(n) complexity for an insertion in the beginning as <a href="https://wiki.python.org/moin/TimeComplexity" rel="nofollow noreferrer">it is written here</a></p>
  <pre><code>import time
  
  for p in [3,4,5,6,7]:
  
      n = 10**p
      print(&quot;n =&quot;, n, &quot;:&quot;)
      
      # Creation of a list [0, 1, ..., n]
      li = list(range(n))
      
      start = time.perf_counter()
      # Adding item at the end
      li.append('a')
      stop = time.perf_counter()
      duration = round((stop - start)*1000, 3)
      
      print(&quot;Time for insertion at the end :&quot;, duration, &quot;ms&quot;)
      
      start = time.perf_counter()
      # Adding item at the beginning
      li.insert(0,'a')
      stop = time.perf_counter()
      duration = round((stop - start)*1000, 3)
  
      print(&quot;Time for insertion at the beginning :&quot;, duration, &quot;ms&quot;)
      print()
  </code></pre>
  <p>And the result :</p>
  <pre><code>n = 1000 :
  Time for insertion at the end : 0.001 ms
  Time for insertion at the beginning : 0.001 ms
  
  n = 10000 :
  Time for insertion at the end : 0.003 ms
  Time for insertion at the beginning : 0.007 ms
  
  n = 100000 :
  Time for insertion at the end : 0.036 ms
  Time for insertion at the beginning : 0.098 ms
  
  n = 1000000 :
  Time for insertion at the end : 0.05 ms
  Time for insertion at the beginning : 1.001 ms
  
  n = 10000000 :
  Time for insertion at the end : 0.257 ms
  Time for insertion at the beginning : 11.453 ms
  </code></pre>
  <p>So, the insertion in the beginning is clearly O(n) but the insertion at the end is clearly not O(1).</p>
  <p>Can anybody explain this to me ?</p>
  <p>config: Python 3.8.5 on Ubuntu 20.04.1 LTS</p>
  <p>So, I tried with timeit (as suggested) and the results are as they should be.</p>
  <p>at the beginning O(n):</p>
  <pre><code>&gt;&gt;&gt; timeit.timeit(&quot;liste.insert(0,'a')&quot;,setup='liste = list(range(10**3))', number=1000)
  0.0012012630177196115
  &gt;&gt;&gt; timeit.timeit(&quot;liste.insert(0,'a')&quot;,setup='liste = list(range(10**4))', number=1000)
  0.008087130001513287
  &gt;&gt;&gt; timeit.timeit(&quot;liste.insert(0,'a')&quot;,setup='liste = list(range(10**5))', number=1000)
  0.06115017700358294
  &gt;&gt;&gt; timeit.timeit(&quot;liste.insert(0,'a')&quot;,setup='liste = list(range(10**6))', number=1000)
  1.0330771339940839
  &gt;&gt;&gt; timeit.timeit(&quot;liste.insert(0,'a')&quot;,setup='liste = list(range(10**7))', number=1000)
  11.236097862012684
  </code></pre>
  <p>at the end O(1):</p>
  <pre><code>&gt;&gt;&gt; timeit.timeit(&quot;liste.append('a')&quot;,setup='liste = list(range(10**3))', number=1000000)
  0.05697788399993442
  &gt;&gt;&gt; timeit.timeit(&quot;liste.append('a')&quot;,setup='liste = list(range(10**4))', number=1000000)
  0.05759519099956378
  &gt;&gt;&gt; timeit.timeit(&quot;liste.append('a')&quot;,setup='liste = list(range(10**5))', number=1000000)
  0.05135001099552028
  &gt;&gt;&gt; timeit.timeit(&quot;liste.append('a')&quot;,setup='liste = list(range(10**6))', number=1000000)
  0.0584335429884959
  &gt;&gt;&gt; timeit.timeit(&quot;liste.append('a')&quot;,setup='liste = list(range(10**7))', number=1000000)
  0.04910806700354442
  </code></pre>
  <p>Since timeit execute the setup only once, it adds one element over and over in the same list.</p>
  <p>So I tried this:</p>
  <pre><code>import time
  
  for p in [3,4,5,6,7]:
      
          n = 10**p
          print(&quot;n =&quot;, n, &quot;:&quot;)
          
          # Creation of a list [0, 1, ..., n]
          li = list(range(n))
          
          for j in range(3):
              start = time.perf_counter()
              # Adding item at the end
              li.append('a')
              stop = time.perf_counter()
              duration = round((stop - start)*1000, 3)
              
              print(&quot;Time for insertion at the end :&quot;, duration, &quot;ms&quot;)
          
  
          for j in range(3):
              start = time.perf_counter()
              # Adding item at the beginning
              li.insert(0,'a')
              stop = time.perf_counter()
              duration = round((stop - start)*1000, 3)
  
              print(&quot;Time for insertion at the beginning :&quot;, duration, &quot;ms&quot;)
          
          print()
  </code></pre>
  <p>and the results:</p>
  <pre><code>n = 1000 :
  Time for insertion at the end : 0.004 ms
  Time for insertion at the end : 0.0 ms
  Time for insertion at the end : 0.0 ms
  Time for insertion at the beginning : 0.001 ms
  Time for insertion at the beginning : 0.001 ms
  Time for insertion at the beginning : 0.001 ms
  
  n = 10000 :
  Time for insertion at the end : 0.002 ms
  Time for insertion at the end : 0.0 ms
  Time for insertion at the end : 0.0 ms
  Time for insertion at the beginning : 0.007 ms
  Time for insertion at the beginning : 0.006 ms
  Time for insertion at the beginning : 0.006 ms
  
  n = 100000 :
  Time for insertion at the end : 0.042 ms
  Time for insertion at the end : 0.001 ms
  Time for insertion at the end : 0.001 ms
  Time for insertion at the beginning : 0.113 ms
  Time for insertion at the beginning : 0.099 ms
  Time for insertion at the beginning : 0.087 ms
  
  n = 1000000 :
  Time for insertion at the end : 0.064 ms
  Time for insertion at the end : 0.001 ms
  Time for insertion at the end : 0.001 ms
  Time for insertion at the beginning : 1.362 ms
  Time for insertion at the beginning : 1.144 ms
  Time for insertion at the beginning : 0.943 ms
  
  n = 10000000 :
  Time for insertion at the end : 0.336 ms
  Time for insertion at the end : 0.002 ms
  Time for insertion at the end : 0.001 ms
  Time for insertion at the beginning : 15.727 ms
  Time for insertion at the beginning : 15.441 ms
  Time for insertion at the beginning : 13.837 ms
  </code></pre>
  <p>So it's just the &quot;first access&quot; to the list that takes some extra time. If I change the order, the extra time is on the insertion at the beginning.</p>
  <p>Still, my curiosity isn't satisfied. Why is there this latency, that depends on the size of the list, in the first access? (sorry for the long post)</p>