What is the time complexity of popping an element from a dict in Python?

This is kind of a combinatorics problem. I have a very large list, all_possible—which stores all of the possible values—and a very large dict, present, which stores all of the actually present values, e.g.:

all_possible = [1, 2, 3, 4, 5]
present = {1: 'some_value', 3: 'some_other_value'}

Currently, my search looks a bit like:

for key in all_possible:
    value = present.get(key, None)
    if value is None:
        do_something_if_key_not_present()
    else:
        do_something_if_key_is_present()

This works nicely, since for each iteration there is only one lookup in the dictionary, and the average lookup time for a Python dictionary is O(1).

However, amortized worst case lookup time is O(N), and since the dictionary can be so huge (millions of elements), one of the optimizations I've considered involves popping the elements from the dict as I traverse (so subsequent lookups have a smaller search space):

for key in all_possible:
    value = present.pop(key, None)  # this line changes, dict shrinks
    if value is None:
        do_something_if_key_not_present()
    else:
        do_something_if_key_is_present()

My question is what is the time complexity of the dictionary pop? I know that average case pop operations in structures like list are O(N), but I cannot find any reliable documentation that denotes the complexity of popping from a dict. If it ends up being O(1), this may speed up my search, but if it's any higher, I might be hurting myself.