Why exactly are .values() and .keys() considered O(1)?

Question

Couldnt track down a solid enough reasoning for why dictionary functions such as .values() and .keys() are considered to be O(1) in big O notation. (not sure if .items() is also considered O(1) )

Answer 1

It is likely that the reference you found to .keys() and .values() (and .items()) being O(1) emphasized the performance because it is a contrast to Python 2, where those functions returned lists and required O(N) time to copy references to all the relevant objects out of the dictionary.

Iterating on the view objects returned by those methods in Python 3 will still take O(N) time, as there's no way to avoid visiting each item, since that's the whole point of iteration. The keys and items views do offer O(1) membership tests (e.g. (somekey, somevalue) in somedict.items()), which is a lot more efficient than searching for an item in a list.

Answer 2

I am not versed in python, but I found this:

Dictionary view objects

The objects returned by dict.keys(), dict.values() and dict.items() are view objects. They provide a dynamic view on the dictionary’s entries, which means that when the dictionary changes, the view reflects these changes.

Dictionary views can be iterated over to yield their respective data, [...]

Which means that dict.keys() and such don't return a new object, but just a thin wrapper that can iterate over the dictionary. So getting this view is O(1). Iterating over elements it's not.