Time Complexity of finding the first item in a dictionary in Python 3.7+

Question

Since Python 3.7, dictionaries preserve order based on insertion.

It seems like you can get the first item in a dictionary using next(iter(my_dict))?

My question is around the Big O time complexity of that operation?

Can I regard next(iter(my_dict)) as a constant time (O(1)) operation? Or what's the best way to retrieve the first item in the dictionary in constant time?

The reason I'm asking is that I'm hoping to use this for coding interviews, where there's a significant emphasis on the time complexity of your solution, rather than how fast it runs in milliseconds.

Answer 1

It's probably the best way (actually you're getting the first key now, next(iter(d.values())) gets your value).

This operation (any iteration through keys, values or items for combined tables at least) iterates through an array holding the dictionary entries:

PyDictKeyEntry *entry_ptr = &DK_ENTRIES(k)[i];
while (i < n && entry_ptr->me_value == NULL) {
    entry_ptr++;
    i++;
}

entry_ptr->me_value holds the value for each respective key.

If your dictionary is freshly created, this finds the first inserted item during the first iteration (the dictionary entries array is append-only, hence preserving order).

If your dictionary has been altered (you've deleted many of the items) this might, in the worse case, result in O(N) to find the first (among remaining items) inserted item (where N is the total number of original items). This is due to dictionaries not resizing when items are removed and, as a result, entry_ptr->me_value being NULL for many entries.

Note that this is CPython specific. I'm not aware of how other implementations of Python implement this.