Why is the time complexity of Python’s list.append() method O(1)?

by

It’s amortized O(1), not O(1).

Let’s say the list reserved size is 8 elements and it doubles in size when space runs out. You want to push 50 elements.

The first 8 elements push in O(1).
The nineth triggers reallocation and 8 copies, followed by an O(1) push.
The next 7 push in O(1).
The seventeenth triggers reallocation and 16 copies, followed by an O(1) push.
The next 15 push in O(1).
The thirty-third triggers reallocation and 32 copies, followed by an O(1) push.
The next 31 push in O(1). This continues as the size of list is doubled again at pushing the 65th, 129th, 257th element, etc..

So all of the pushes have O(1) complexity, we had 64 copies at O(1), and 3 reallocations at O(n), with n = 8, 16, and 32. Note that this is a geometric series and asymptotically equals O(n) with n = the final size of the list. That means the whole operation of pushing n objects onto the list is O(n). If we amortize that per element, it’s O(n)/n = O(1).

More Related Contents:

  1. Change sign of elements with an odd sum of indices
  2. How to fix: “UnicodeDecodeError: ‘ascii’ codec can’t decode byte”
  3. Writing a Python list of lists to a csv file
  4. How to write a Python module/package?
  5. How to scroll the background surface in PyGame?
  6. Python: pop from empty list
  7. Check if a string in a Pandas DataFrame column is in a list of strings
  8. Can Python pickle lambda functions?
  9. Naturally sorting Pandas DataFrame
  10. How To Get All The Contiguous Substrings Of A String In Python?
  11. is it possible to run pygame or pyglet in a browser?
  12. How to normalize json correctly by Python Pandas
  13. Is it good practice to use `import __main__`?
  14. Python3 correct way to import relative or absolute?
  15. Use Multiple Character Delimiter in Python Pandas read_csv
  16. Cancellable threading.Timer in Python
  17. Python OrderedDict not keeping element order [duplicate]
  18. What is time complexity of a list to set conversion?
  19. pandas: replace string with another string
  20. Type hinting in Python 2
  21. How to apply a function to each sublist of a list in python?
  22. filter items in a python dictionary where keys contain a specific string
  23. python 2.7 equivalent of built-in method int.from_bytes
  24. UnboundLocalError: local variable … referenced before assignment [duplicate]
  25. Printing on the same line with time.sleep()
  26. Python os.path.join() on a list
  27. Runtime of python’s if substring in string
  28. How do I get Python libraries in pyspark?
  29. What is the best approach in python: multiple OR or IN in if statement?
  30. Get body text of an email using python imap and email package

Leave a Comment