Actually, in a program that dynamically creates a class, and then deletes it, you would expect a O(1) complexity.  adding children at the end, and searching from the end, is a way to achieve this.
While I admit that I oversaw the exact requirement for __bases__, I think that allowing for a "None" to be sufficient when the class is being deleted is an important improvement.  I realize that the therotetical worst case is O(n), but the practical common case is still O(1)