Diamond problem in Python - Time & Space Complexity

Time Complexity: Diamond problem

O(n)

Understanding Time Complexity

When working with multiple inheritance in Python, the diamond problem shows how methods are found and called.

We want to understand how the time to find a method grows as the inheritance chain grows.

Scenario Under Consideration

Analyze the time complexity of method lookup in this diamond inheritance example.

class A:
    def method(self):
        return "A"

class B(A):
    def method(self):
        return "B"

class C(A):
    def method(self):
        return "C"

class D(B, C):
    pass

obj = D()
result = obj.method()
    

This code defines a diamond shape inheritance and calls a method on the bottom class.

Identify Repeating Operations

Python looks for the method by checking classes in a specific order.

• Primary operation: Searching classes in the method resolution order (MRO).
• How many times: At most once per class in the method resolution order.

How Execution Grows With Input

As the number of classes in the inheritance chain grows, Python checks each class once in order.

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

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 in the inheritance chain.

Common Mistake

[X] Wrong: "Method lookup happens instantly no matter how many classes there are."

[OK] Correct: Python must check each class in order until it finds the method, so more classes mean more checks.

Interview Connect

Understanding how method lookup works helps you reason about multiple inheritance and its costs in real code.

Self-Check

What if we added caching for method lookups? How would that change the time complexity?