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.

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.

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