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?"

Practice

1. What does the how parameter in merge() control when joining two DataFrames?

easy

A. The data types of the columns

B. The columns to join on

C. The order of rows in the result

D. The type of join: inner, left, right, or outer

Solution

1. Step 1: Understand the role of how in merge()

   The how parameter specifies the type of join to perform, such as inner, left, right, or outer join.

2. Step 2: Differentiate from other parameters

   Other parameters like on specify columns to join on, but how controls how rows are matched and combined.

3. Final Answer:

   The type of join: inner, left, right, or outer -> Option D

4. Quick Check:

   how = join type [OK]

Hint: Remember: 'how' means join type like SQL joins [OK]

Common Mistakes:

• Confusing 'how' with 'on' parameter
• Thinking 'how' controls column selection
• Assuming 'how' changes data types

2. Which of the following is the correct syntax to merge two DataFrames df1 and df2 on the column 'id' using an inner join?

easy

A. pd.merge(df1, df2, join='id', how='inner')

B. pd.merge(df1, df2, on='id', how='inner')

C. df1.merge(df2, on='id', type='inner')

D. pd.merge(df1, df2, on='id', join='inner')

Solution

1. Step 1: Identify correct parameter names

   The correct parameters for merging are on for the column and how for join type.

2. Step 2: Check syntax correctness

   pd.merge(df1, df2, on='id', how='inner') uses pd.merge(df1, df2, on='id', how='inner'), which is the correct syntax. Other options use incorrect parameter names like join or type.

3. Final Answer:

   pd.merge(df1, df2, on='id', how='inner') -> Option B

4. Quick Check:

   Correct parameters: on, how [OK]

Hint: Use 'on' for columns and 'how' for join type [OK]

Common Mistakes:

• Using 'join' instead of 'how'
• Using 'type' instead of 'how'
• Mixing parameter names

3. Given the following code, what is the output of result?

import pandas as pd

df1 = pd.DataFrame({'key': ['A', 'B', 'C'], 'val1': [1, 2, 3]})
df2 = pd.DataFrame({'key': ['B', 'C', 'D'], 'val2': [4, 5, 6]})

result = pd.merge(df1, df2, on='key', how='inner')
print(result)

medium

A. key val1 val2
0 B 2 4
1 C 3 5

B. key val1 val2
0 A 1 4
1 B 2 5
2 C 3 6

C. key val1 val2
0 A 1 NaN
1 B 2 4
2 C 3 5

D. key val1 val2
0 B 2 NaN
1 C 3 NaN
2 D NaN 6

Solution

1. Step 1: Understand inner join on 'key'

   Inner join keeps only rows with keys present in both DataFrames: 'B' and 'C'.

2. Step 2: Match rows and combine columns

   For 'B': val1=2, val2=4; for 'C': val1=3, val2=5. Rows with 'A' and 'D' are excluded.

3. Final Answer:

   key val1 val2 0 B 2 4 1 C 3 5 -> Option A

4. Quick Check:

   Inner join = intersection keys [OK]

Hint: Inner join keeps only common keys [OK]

Common Mistakes:

• Including keys not in both DataFrames
• Confusing inner with outer join
• Misaligning values for keys

4. What is wrong with this code snippet?

import pandas as pd

df1 = pd.DataFrame({'id': [1, 2], 'val': ['A', 'B']})
df2 = pd.DataFrame({'key': [1, 3], 'val2': ['X', 'Y']})

result = pd.merge(df1, df2, on='id', how='left')
print(result)

medium

A. DataFrames must have the same number of rows to merge

B. The 'how' parameter cannot be 'left'

C. The merge function is missing the 'left_on' and 'right_on' parameters

D. Column 'id' does not exist in both DataFrames

Solution

1. Step 1: Check columns used for merging

   The code tries to merge on column 'id', but df2 has 'key' column instead of 'id'.

2. Step 2: Understand merge requirements

   For merging on different column names, left_on and right_on must be used, or columns must have the same name.

3. Final Answer:

   The merge function is missing the 'left_on' and 'right_on' parameters -> Option C

4. Quick Check:

   Merge columns must exist in both DataFrames or be specified [OK]

Hint: Check column names exist in both DataFrames or specify left_on/right_on [OK]

Common Mistakes:

• Assuming merge works with different column names without specifying
• Thinking 'how' parameter is invalid
• Believing row counts must match

5. You have two DataFrames: orders with columns order_id, customer_id, and amount, and customers with columns cust_id and name. How do you merge them to get all orders with customer names, even if some customers are missing in customers DataFrame?

hard

A. pd.merge(orders, customers, left_on='customer_id', right_on='cust_id', how='left')

B. pd.merge(orders, customers, on='customer_id', how='inner')

C. pd.merge(orders, customers, left_on='cust_id', right_on='customer_id', how='right')

D. pd.merge(orders, customers, on='cust_id', how='outer')

Solution

1. Step 1: Identify join keys with different column names

   Orders use 'customer_id', customers use 'cust_id', so use left_on and right_on to specify.

2. Step 2: Choose join type to keep all orders

   Use how='left' to keep all rows from orders, even if no matching customer exists.

3. Final Answer:

   pd.merge(orders, customers, left_on='customer_id', right_on='cust_id', how='left') -> Option A

4. Quick Check:

   Left join keeps all left rows [OK]

Hint: Use left_on/right_on for different keys and 'left' to keep all left rows [OK]

Common Mistakes:

• Using 'on' with different column names
• Using inner join and losing unmatched orders
• Swapping left_on and right_on