Method Resolution Order (MRO) in Python - Time & Space Complexity

Time Complexity: Method Resolution Order (MRO)

O(n)

Understanding Time Complexity

When Python looks for a method in classes with multiple inheritance, it follows a specific order called Method Resolution Order (MRO).

We want to understand how the time to find a method grows as the number of classes in the inheritance chain increases.

Scenario Under Consideration

Analyze the time complexity of Python finding a method using MRO.

class A:
    def greet(self):
        print("Hello from A")

class B(A):
    pass

class C(B):
    pass

obj = C()
obj.greet()
    

This code calls greet on an object of class C, which inherits from B and A. Python searches classes in MRO to find greet.

Identify Repeating Operations

Identify the steps Python takes to find the method.

• Primary operation: Checking each class in the MRO list for the method.
• How many times: Up to the number of classes in the inheritance chain.

How Execution Grows With Input

As the number of classes grows, Python checks each class one by one until it finds the method.

Input Size (number of classes)	Approx. Operations (class checks)
3	Up to 3 checks
10	Up to 10 checks
100	Up to 100 checks

Pattern observation: The number of checks grows directly with the number of classes to search.

Final Time Complexity

Time Complexity: O(n)

This means the time to find a method grows linearly with the number of classes Python must check in the MRO.

Common Mistake

[X] Wrong: "Python finds methods instantly no matter how many classes there are."

[OK] Correct: Python checks classes one by one in order, so more classes mean more checks and more time.

Interview Connect

Understanding MRO time helps you explain how Python handles multiple inheritance efficiently and why class design matters for performance.

Self-Check

What if Python cached method lookups? How would that change the time complexity?