CODEWITHSUNDEEP
pythonpython-3.xbig-o
Imre_G
Imre_G

Reputation: 2535

Does looping through a reversed(list) add to the time complexity of my function?

Short but simple question. I have been studying time complexity for a coding interview and I can not find a concise answer to this. I am aware that this question exists on SO. What is the time complexity of Python List Reverse?.

Python has two methods for looping through lists. You can either loop through list.reverse() which reverses the list in place at time complexity O(n) or you can loop through reversed(list). My question is: does using reversed(list) also come at complexity O(n) or not?

I can imagine two possible answers, either it actually reverses the list (in which case I would say: Yes, it does add O(n)) or it just loops through the list from the other side (in which case I would say, No: it doesn't). Can anyone give me a definitive answer to this?

Upvotes: 6

Views: 1860

Answers (1)

kabanus
kabanus

Reputation: 25895

The reversed builtin like many others in Python 3 return an iterator, and hence does not cost an extra n iterations. When dealing with big-O notation it won't matter, but you are interested in the factor, so no, 

for i in reversed(my_list):

passes the list exactly once. This is exactly the point of these type of helper functions.

Note you could have used

for i in my_list[::-1]:

which is a common way to iterate, but using slicing already returns a list - so similarly to my_list.reverse, an extra n as well.

Upvotes: 11

Related Questions