The implementation of OrderedDict.__delitem__ in Python 3.7 is as follows:

def __delitem__(self, key, dict_delitem=dict.__delitem__):
    'od.__delitem__(y) <==> del od[y]'
    # Deleting an existing item uses self.__map to find the link which gets
    # removed by updating the links in the predecessor and successor nodes.
    dict_delitem(self, key)
    link = self.__map.pop(key)
    link_prev = link.prev
    link_next = link.next
    link_prev.next = link_next
    link_next.prev = link_prev
    link.prev = None
    link.next = None

This code does 3 things:

• Remove an item from the internal key-value dictionary.
• Remove a node from the dictionary holding linked list nodes.
• Delete an item from a doubly linked list.

Since the average case complexity of all the above operations is constant, the average case complexity of OrderedDict.__delitem__ is constant as well.

Do note however that the worst case complexity of deleting a key from a dictionary is O(n), so the same applies for ordered dictionaries as well.

Some rationale for why it is being claimed to be O(1):

The clear() method is actually just assigning the internal dictionary structures to new empty values (as can be seen in the source). The seemingly O(n) part is a result of decrementing reference counts, and other GC-related stuff. But this is purely a function of the GC approach that CPython uses (i.e. reference counting); you can envision different approaches that wouldn't require explicit cleanup like this, or where the cleanup would happen much later (or even be amortized away). Since ideally the time complexity of clear() shouldn't depend on the underlying GC approach, all GC-related parts are omitted, making it "O(1)". IMO this is mostly a definitional argument than anything else, but this is at least some justification.