CODEWITHSUNDEEP
pythoncomplexity-theorytuples
Ivan
Ivan

Reputation: 1133

Time complexity of accessing an element in a tuple

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

But I didn't find anything about tuples.

The access time for

data_structure[i]

What about tuple? Is it O(n) like for a linked list or O(1) like for an array?

Upvotes: 11

Views: 14356

Answers (4)

Alex Smith
Alex Smith

Reputation: 1535

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 it's O(1) for them too.

Upvotes: 3

marr75
marr75

Reputation: 5725

Lists and tuples are indexable in the exact same way arrays are in other languages.

A simplified explanation is that space is allocated for references to objects, those references take up a uniform amount of space, and any index is simply multiplied by the size of the reference to get an offset into the array. This gives constant, O(1), access for lists and tuples.

Upvotes: 4

David Heffernan
David Heffernan

Reputation: 613491

It's O(1) for both list and tuple. They are both morally equivalent to an integer indexed array.

Upvotes: 11

Daren Thomas
Daren Thomas

Reputation: 70344

It should be O(1), because it really is only a list.

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

Upvotes: 1

Related Questions