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.

Any solution will have to read the values associated to each key of each dictionary; so you won't be able to drop under \$\mathcal{O}(n\times{}m)\$ where \$m\$ is the length of each dictionary. This is pretty much what you are doing, but the if k not in keep_keys call slows things a bit as it is \$\mathcal{O}(m)\$ when it could be \$\mathcal{O}(1)\$ by using a set or a dictionary.

If you change the keep_keys list into a set you simplify the logic a bit: as soon as you find a key whose value is not None you can add it into the set.

dicts = [{'a': 1, 'b': None, 'c': 4}, {'a': 2, 'b': None, 'c': 3}, {'a': None, 'b': None, 'c': 3}]
expected = [{'a': 1, 'c': 4}, {'a': 2, 'c': 3}, {'a': None, 'c': 3}]

keep_keys = set()

for d in dicts:
    for key, value in d.items():
        if value is not None:
            keep_keys.add(key)

remove_keys = set(d) - keep_keys

for d in dicts:
    for k in remove_keys:
        del d[k]

print dicts == expected

This code, as your original one, assume that there is at least one item in dicts; otherwise set(d) will generate an exception as the variable d is not defined yet.

But this code mixes the actual logic with some tests. You should wrap it in a function to ease reusability and put the testing code under an if __name__ == '__main__': clause:

def filter_nones(dictionaries):
    if not dictionaries:
        return

    keep_keys = set()

    for dict_ in dictionaries:
        for key, value in dict_.iteritems():
            if value is not None:
                keep_keys.add(key)

    remove_keys = set(dict_) - keep_keys

    for dict_ in dictionaries:
        for key in remove_keys:
            del dict_[key]


if __name__ == '__main__':
    dicts = [
            {'a': 1, 'b': None, 'c': 4},
            {'a': 2, 'b': None, 'c': 3},
            {'a': None, 'b': None, 'c': 3},
    ]
    expected = [
            {'a': 1, 'c': 4},
            {'a': 2, 'c': 3},
            {'a': None, 'c': 3},
    ]

    filter_nones(dicts)
    print dicts == expected

To delete a key regardless of whether it is in the dictionary, use the two-argument form of dict.pop():

my_dict.pop('key', None)

This will return my_dict[key] if key exists in the dictionary, and None otherwise. If the second parameter is not specified (i.e. my_dict.pop('key')) and key does not exist, a KeyError is raised.

To delete a key that is guaranteed to exist, you can also use

del my_dict['key']

This will raise a KeyError if the key is not in the dictionary.