Why is the time complexity of appending items at the end of the dynamic array 0(1)

Question

I would like to know why the time complexity for appending element at the end of the dynamic array is 0(1)

Here I have taken into account that the dynamic array isnt full yet.

for example in python,imagine a list of size 6 and only 3 elements are filled:

a = [ 1, 2, 3 , _ , _ , _ ] 
a.append(4)

now when I add an element to the 3rd index why will the time complexity be 0(1) and not 0(n) ? Is there a pointer that points to the last element of the array ? Or is there some other mechanism underneath?

Because to add the element to the 3rd index i need to traverse to the 3rd index and add the element right? or does append work differently?

Your question talks about dynamic arrays, but your python example uses a list, not an array. — Raymond Chen, Jun 08 '21 at 00:09
In which case, the elements can be accessed by index in O(1) time. — Raymond Chen, Jun 08 '21 at 01:29
Some good answers here: https://stackoverflow.com/questions/3917574/how-is-pythons-list-implemented — zr0gravity7, Jun 08 '21 at 13:23

score 0 · Answer 1 · edited Jun 25 '21 at 11:22

Yes, basically dynamic arrays are internally working as normal arrays. When you keep on adding elements to the dynamic array, it's size keeps on increasing internally. Since dynamic arrays are internally using normal arrays hence it uses indexing to add and retrieve elements from the array. Thus dynamic arrays will also be having the time complexity if O(1) when you add element to the dynamic array.

Why is the time complexity of appending items at the end of the dynamic array 0(1)

1 Answers1