Inner join in Data Analysis Python - Time & Space Complexity

Time Complexity: Inner join

O(n * m)

Understanding Time Complexity

When we combine two tables using an inner join, we want to know how the time to do this grows as the tables get bigger.

We ask: How does the work increase when the number of rows in each table grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import pandas as pd

df1 = pd.DataFrame({'key': [1, 2, 3], 'value1': ['A', 'B', 'C']})
df2 = pd.DataFrame({'key': [2, 3, 4], 'value2': ['X', 'Y', 'Z']})

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

This code joins two tables on a common column called 'key' and keeps only matching rows.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each row in the first table against rows in the second table to find matching keys.
• How many times: For each row in the first table, the algorithm looks for matching rows in the second table.

How Execution Grows With Input

As the number of rows in both tables grows, the number of comparisons grows too.

Input Size (n)	Approx. Operations
10	About 100 checks
100	About 10,000 checks
1000	About 1,000,000 checks

Pattern observation: The work grows much faster than the input size because each row in one table is compared to many rows in the other.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to join grows roughly by multiplying the number of rows in the first table by the number of rows in the second table.

Common Mistake

[X] Wrong: "The inner join time grows only with the size of one table."

[OK] Correct: Because the join must compare rows from both tables, the time depends on both sizes, not just one.

Interview Connect

Understanding how joins scale helps you explain database performance clearly and shows you know what happens behind the scenes.

Self-Check

"What if one table has an index on the join column? How would the time complexity change?"

Practice

1. What does an inner join do when combining two tables?

easy

A. Returns only rows with matching keys in both tables

B. Returns all rows from the first table, matching or not

C. Returns all rows from the second table, matching or not

D. Returns all rows from both tables, matching or not

Solution

1. Step 1: Understand join types

   Inner join returns rows where keys match in both tables only.

2. Step 2: Compare options with definition

   The option 'Returns only rows with matching keys in both tables' describes this behavior correctly.

3. Final Answer:

   Returns only rows with matching keys in both tables -> Option A

4. Quick Check:

   Inner join = matching rows only [OK]

Hint: Inner join keeps only matching rows from both tables [OK]

Common Mistakes:

• Confusing inner join with left or right join
• Thinking inner join returns unmatched rows
• Mixing up join types and their results

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

easy

A. df1.join(df2, on='id', how='outer')

B. pd.concat([df1, df2], axis=1, join='inner')

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

D. df1.merge(df2, on='id', how='left')

Solution

1. Step 1: Identify pandas inner join syntax

   The correct function is pd.merge() with how='inner' and on='id'.

2. Step 2: Check each option

   pd.merge(df1, df2, on='id', how='inner') matches this exactly; others use wrong methods or join types.

3. Final Answer:

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

4. Quick Check:

   pd.merge + how='inner' = inner join [OK]

Hint: Use pd.merge with how='inner' for inner joins [OK]

Common Mistakes:

• Using join() instead of merge() for inner join
• Using wrong join type like 'outer' or 'left'
• Using concat which does not perform join

3. Given two DataFrames:

df1 = pd.DataFrame({'id': [1, 2, 3], 'val1': ['A', 'B', 'C']})
df2 = pd.DataFrame({'id': [2, 3, 4], 'val2': ['X', 'Y', 'Z']})
result = pd.merge(df1, df2, on='id', how='inner')

What is the content of result?

medium

A. {'id': [2, 3], 'val1': ['B', 'C'], 'val2': ['X', 'Y']}

B. {'id': [1, 4], 'val1': ['A', None], 'val2': [None, 'Z']}

C. {'id': [2, 3, 4], 'val1': ['B', 'C', None], 'val2': ['X', 'Y', 'Z']}

D. {'id': [1, 2, 3], 'val1': ['A', 'B', 'C'], 'val2': ['X', 'Y', 'Z']}

Solution

1. Step 1: Identify matching keys for inner join

   Keys in both df1 and df2 are 2 and 3 only.

2. Step 2: Merge rows with matching keys

   Rows with id 2 and 3 combine val1 and val2 columns.

3. Final Answer:

   {'id': [2, 3], 'val1': ['B', 'C'], 'val2': ['X', 'Y']} -> Option A

4. Quick Check:

   Inner join keeps ids 2 and 3 only [OK]

Hint: Inner join keeps only common keys in both DataFrames [OK]

Common Mistakes:

• Including keys not present in both tables
• Confusing inner join with outer join
• Assuming all rows are kept

4. You wrote this code to inner join two DataFrames:

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

But it raises an error. What is the likely cause?

medium

A. Using 'how' parameter incorrectly

B. Missing the 'on' parameter to specify join key

C. DataFrames must be converted to lists first

D. Inner join is not supported by pandas

Solution

1. Step 1: Check required parameters for pd.merge

   pd.merge requires 'on' or 'left_on'/'right_on' to specify join keys.

2. Step 2: Identify missing 'on' parameter

   Code misses 'on' parameter, causing error.

3. Final Answer:

   Missing the 'on' parameter to specify join key -> Option B

4. Quick Check:

   pd.merge needs 'on' key [OK]

Hint: Always specify 'on' column for merge keys [OK]

Common Mistakes:

• Forgetting to specify join keys
• Assuming default join key exists
• Trying to join incompatible data types

5. You have two DataFrames:

df1 = pd.DataFrame({'id': [1, 2, 2, 3], 'val1': ['A', 'B', 'C', 'D']})
df2 = pd.DataFrame({'id': [2, 2, 3], 'val2': ['X', 'Y', 'Z']})
result = pd.merge(df1, df2, on='id', how='inner')

How many rows will result contain after the inner join?

hard

A. 6

B. 4

C. 3

D. 5

Solution

1. Step 1: Identify matching keys and duplicates

   Keys 2 and 3 appear multiple times in both DataFrames.

2. Step 2: Calculate Cartesian product for duplicates

   For id=2: df1 has 2 rows, df2 has 2 rows -> 2*2=4 rows.
   For id=3: df1 has 1 row, df2 has 1 row -> 1*1=1 row.
   Total rows = 4 + 1 = 5 rows.

3. Step 3: Recount carefully

   Recount confirms 5 rows total.

4. Final Answer:

   5 -> Option D

5. Quick Check:

   Duplicates multiply rows in inner join [OK]

Hint: Duplicates multiply rows in inner join result [OK]

Common Mistakes:

• Ignoring duplicate keys causing more rows
• Counting unique keys only
• Assuming one-to-one join always