CODEWITHSUNDEEP
pythonappendamortized-analysis
Sangjin Kim
Sangjin Kim

Reputation: 1061

Why is amortized cost of Python list append is O(1) even though it does not double the capacity when there is no space left?

From the materials found in the web, it seems Python list does not double the capacity when the list is full. https://medium.com/analytics-vidhya/amortized-runtime-analysis-for-python-lists-35e935e290db

Java's ArrayList also uses 1.5 instead of doubling.

I understand the mathematics given in textbooks about amortized analysis of append if the capacity is doubled each time a dynamic array based list is full. From those textbooks, my understanding is that doubling is the minimum to achieve amortized cost of O(1). I also understand that if we increase k slots(i.e 10 slots) each time the list is full, the amortized cost is O(n).

However, in Python, the next capacity is computed using ceil(9n/8+6) when n>9. Can someone explain why the amortized cost of Python append is O(1) even though it does not double the capacity when more space is required like other language lists? Mathematical analysis would be helpful.

Upvotes: 1

Views: 552

Answers (1)

Oldring
Oldring

Reputation: 3

To estimate the single element addition amortized cost we have to divide the total number of elements copied while the buffer expansion by the last number of elements copied. But after n exponential expansions the total number of elements copied is a sum of a geometric progression and the last number of elements copied is just an exponent with the same growth rate as a base. Their ratio have a finite limit for any exponential growth rate greater than 1. Accounting for ceiling and additional constants can not change this limit existence.

Upvotes: 0

Related Questions