Comparison magic methods in Python - Time & Space Complexity

Time Complexity: Comparison magic methods

O(n)

Understanding Time Complexity

We want to understand how fast comparison magic methods run when comparing objects.

How does the time to compare grow as the objects get bigger or more complex?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Box:
    def __init__(self, items):
        self.items = items

    def __eq__(self, other):
        return self.items == other.items

This code defines a class with a comparison method that checks if two boxes have the same items.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing the lists inside the boxes element by element.
• How many times: Once for each item in the list until a difference is found or all items are checked.

How Execution Grows With Input

As the number of items in the boxes grows, the comparison takes longer because it checks each item.

Input Size (n)	Approx. Operations
10	About 10 item comparisons
100	About 100 item comparisons
1000	About 1000 item comparisons

Pattern observation: The work grows roughly in direct proportion to the number of items.

Final Time Complexity

Time Complexity: O(n)

This means the time to compare grows linearly with the number of items in the boxes.

Common Mistake

[X] Wrong: "Comparing two objects always takes the same time no matter their size."

[OK] Correct: The comparison checks each item inside, so bigger objects take more time.

Interview Connect

Knowing how comparison methods scale helps you write efficient code and explain your choices clearly.

Self-Check

"What if the items were stored in a set instead of a list? How would the time complexity change?"