What is the time complexity to get the last index for an array? [duplicate]

Question

array = ["A", "B", "C", "D"]

for the given array it takes O(1) to point to the first index which is 0. So if I type array[0], it takes O(1) to point to "A". But if i write array[-1] which points to the last index 3. Does it iterate through the entire array to get the last index or it knows that the array ends at index 3 by default ? In other words how is array[-1] is implemented in python?

Answer 1

Accessing any array element is in constant time, since it is a known by memory location (i.e. a pointer.)

The array does not need to go through prior elements in order to access the nth element (i.e. it is not like a linked list.) The location of all elements is known before hand and can simply be accessed directly.

Updated thanks to comments.

array[-x] is syntactic sugar for array[len(lst) - x]. So it's still a simple constant access to a pointer and takes no time.

You can see this answer for a bit more info. While it is about C, the concepts should be the same.

Answer 2

Native Python lists are arrays of pointers and accessing any element is O(1).

Note that this is an implementation detail specific to the standard Python implementation, known as CPython. Other language implementations may implement lists differently.