Python tuple time complexity

Question

There is a similar question about hash (dictionaries) and lists, there is also good information here: http://wiki.python.org/moin/TimeComplexity

But I did not find anything about tuples.

Access time for

data_structure[i] 

• for a linked list in the general case O (n)
• for dictionary ~ O (1)

How about a tuple? Is O (n) similar to a linked list, or O (1) as for an array?

Answer 1

This is O (1) for list and tuple. They are both morally equivalent to an integer indexed array.

Answer 2

Lists and tuples are indexed in the same way that arrays are in other languages.

A simplified explanation is that space is allocated for references to objects, these links occupy a single space, and any index is simply multiplied by the size of the link to obtain an offset in the array. This gives constant, O (1) access for lists and tuples.

Answer 3

Getting an item from a linked list is O (n), but Python lists have array-based implementations, so the cost is O (1).

Tuples are also implemented using arrays, so they are also O (1) for them.

Answer 4

It must be O(1) because it is really just a list.

But for python lists, I would expect O(1) too! You might want to think about it again ...