Time complexity of typecasting dictionary to list in Python

If we have a dictionary with 'n' key-value pairs, then, does typecasting it to a list a linear time operation (i.e. O(n))?

1 answer

  • answered 2018-01-13 17:16 John Kugelman

    It's not clear what you mean by "typecasting it to a list". list(d) will return a list of the dictionary's keys. list(d.items()) will return a list of key/value pairs.

    Either way, yes, it's O(n). It can't be faster than O(n) since it obviously has to iterate over all of the dictionary items. And there's no reason it would be slower than O(n).