merge() for SQL-style joins in Data Analysis Python - Time & Space Complexity

Time Complexity: merge() for SQL-style joins

O(n + m)

Understanding Time Complexity

When we join two tables using merge(), we want to know how the time needed changes as the tables get bigger.

We ask: How does the work grow when the number of rows in each table increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import pandas as pd

left = pd.DataFrame({'key': [1, 2, 3], 'value_left': ['A', 'B', 'C']})
right = pd.DataFrame({'key': [2, 3, 4], 'value_right': ['X', 'Y', 'Z']})

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

This code joins two tables on a common column called 'key' using an inner join.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Building a hash table from one table's keys and looking up keys from the other table.
• How many times: Hash table construction processes each row once in one table (O(m)), and each row in the other table performs a constant-time lookup (O(n)).

How Execution Grows With Input

As the number of rows in both tables grows, the work to find matching keys grows roughly in proportion to the sum of their sizes.

Input Size (n)	Approx. Operations
10	About 20 operations
100	About 200 operations
1000	About 2,000 operations

Pattern observation: Doubling the size of both tables roughly doubles the work needed.

Final Time Complexity

Time Complexity: O(n + m)

This means the time grows roughly by adding the number of rows in the first table (n) and the number of rows in the second table (m).

Common Mistake

[X] Wrong: "The merge() function runs in quadratic time O(n*m) like nested loops."

[OK] Correct: Pandas uses an efficient hash join: it builds a hash table for (usually) the smaller table and performs constant-time lookups for rows from the other table, resulting in linear time.

Interview Connect

Understanding how joins scale helps you explain data processing choices clearly and shows you can think about efficiency in real data tasks.

Self-Check

"What if one table is already sorted by the join key? How would the time complexity change?"