title: What is the time complexity of popping an element from a dict in Python?
body: <p>This is kind of a combinatorics problem. I have a very large list, <code>all_possible</code>&mdash;which stores all of the possible values&mdash;and a very large <code>dict</code>, <code>present</code>, which stores all of the actually present values, e.g.:</p>
  
  <pre><code>all_possible = [1, 2, 3, 4, 5]
  present = {1: 'some_value', 3: 'some_other_value'}
  </code></pre>
  
  <p>Currently, my search looks a bit like:</p>
  
  <pre><code>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()
  </code></pre>
  
  <p>This works nicely, since for each iteration there is only one lookup in the dictionary, and the average lookup time for a Python dictionary <a href="https://wiki.python.org/moin/TimeComplexity" rel="noreferrer">is O(1)</a>. </p>
  
  <p>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):</p>
  
  <pre><code>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()
  </code></pre>
  
  <p>My question is <strong>what is the time complexity of the dictionary <code>pop</code>?</strong> I know that average case <code>pop</code> operations in structures like <code>list</code> are O(N), but I cannot find any reliable documentation that denotes the complexity of popping from a <code>dict</code>. If it ends up being O(1), this may speed up my search, but if it's any higher, I might be hurting myself.</p>