Left and right joins in Data Analysis Python - Time & Space Complexity

Time Complexity: Left and right joins

O(n)

Understanding Time Complexity

When we join two tables, we combine their rows based on matching keys.

We want to know how the time to join grows as the tables get bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import pandas as pd

n = 1000
left = pd.DataFrame({'key': range(n), 'value_left': range(n)})
right = pd.DataFrame({'key': range(n//2, 3*n//2), 'value_right': range(n)})

result = pd.merge(left, right, how='left', on='key')

This code performs a left join of two data tables on a key column.

Identify Repeating Operations

• Primary operation: Matching each row in the left table to rows in the right table by key.
• How many times: Once for each row in the left table (n times).

How Execution Grows With Input

As the left table grows, the join checks more rows to find matches.

Input Size (n)	Approx. Operations
10	About 10 key lookups
100	About 100 key lookups
1000	About 1000 key lookups

Pattern observation: The number of operations grows roughly in direct proportion to the size of the left table.

Final Time Complexity

Time Complexity: O(n)

This means the time to join grows linearly with the number of rows in the left table.

Common Mistake

[X] Wrong: "The join time depends on the size of both tables multiplied together."

[OK] Correct: Efficient joins use indexes or hashing to avoid checking every pair, so time depends mostly on the left table size.

Interview Connect

Understanding join time helps you explain how data grows and affects performance in real projects.

Self-Check

"What if we changed the join from left to full outer join? How would the time complexity change?"