CODEWITHSUNDEEP
pythonpython-3.x
somesh
somesh

Reputation: 63

Time complexity of reversed() in Python 3

What is the time complexity of reversed() in Python 3?

I think the answer would be O(1) but I want to clarify whether it is right or wrong.

Upvotes: 3

Views: 2004

Answers (1)

user8408080
user8408080

Reputation: 2468

reversed(some_list) always takes about 120ns to finish on my machine, which is a clear sign of O(1) time complexity. This is because this function does not actually change any values, it just returns a list_reverseiterator, which iterates the list backwards. This object is very similar to a normal generator, as it its elements get consumed, when you are, for example, calling list on it:

In [10]: a = [i for i in range(5)]

In [11]: b = reversed(a)

In [12]: b
Out[12]: <list_reverseiterator at 0x7f11fe3615b0>

In [13]: list(b)
Out[13]: [4, 3, 2, 1, 0]

In [14]: b
Out[14]: <list_reverseiterator at 0x7f11fe3615b0>

In [15]: list(b)
Out[15]: []

Upvotes: 5

Related Questions