title: Complexity of deleting a key from python ordered dict
body: <p>Deleting a key from a python <code>dict</code> or <code>defaultdict</code> in python is O(1) operation, <a href="https://www.ics.uci.edu/~brgallar/week8_2.html" rel="noreferrer">as mentioned here</a> and <a href="https://wiki.python.org/moin/TimeComplexity" rel="noreferrer">here</a>. To remove a key from <code>OrderedDict</code>, we can either use <code>del d[key]</code> or use <code>popitem()</code> method, as mentioned in <a href="https://docs.python.org/3.6/library/collections.html#collections.OrderedDict.popitem" rel="noreferrer">the docs</a>.</p>
  
  <p>What is the underlying implementation of <code>OrderedDict</code> and the time complexity of <code>del</code> operation?</p>
  
  <p>Edit: This answer <a href="https://stackoverflow.com/questions/8176513/ordereddict-performance-compared-to-deque">OrderedDict performance (compared to deque)</a> , refers to the complexity of <code>del</code> in <code>OrderedDict</code> as being O(1). However, how can we justify it at implementation detail level?</p>