join functions (left_join, inner_join) in R Programming - Time & Space Complexity

Time Complexity: join functions (left_join, inner_join)

O(n)

Understanding Time Complexity

When we use join functions like left_join or inner_join, we combine two tables based on matching values.

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

Scenario Under Consideration

Analyze the time complexity of the following R code using dplyr joins.

library(dplyr)

# Two example data frames
df1 <- data.frame(id = 1:1000, value1 = rnorm(1000))
df2 <- data.frame(id = sample(1:1500, 800), value2 = rnorm(800))

# Perform a left join on 'id'
result <- left_join(df1, df2, by = "id")

This code joins two tables by matching the id column, keeping all rows from the first table.

Identify Repeating Operations

Look for repeated steps that take time as input grows.

• Primary operation: Matching each row in the first table to rows in the second table by key.
• How many times: For each of the n rows in the first table, the join looks up matching rows in the second table.

How Execution Grows With Input

As the first table grows, the join needs to find matches for more rows.

Input Size (n)	Approx. Operations
10	About 10 lookups in second table
100	About 100 lookups in second table
1000	About 1000 lookups in second table

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

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Joining two tables always takes time proportional to the product of their sizes (like n x m)."

[OK] Correct: Efficient join functions use fast lookups (like hash tables) to avoid checking every pair, so time depends mostly on the first table size.

Interview Connect

Understanding how join operations scale helps you explain data processing choices clearly and confidently in real projects or interviews.

Self-Check

"What if the second table is much larger than the first? How would that affect the time complexity of the join?"

Practice

1. What does the left_join function do in R's dplyr package?

easy

A. Removes all rows that have any missing values.

B. Keeps only rows that match in both tables.

C. Keeps all rows from the second table and adds matching rows from the first table.

D. Keeps all rows from the first table and adds matching rows from the second table.

Solution

1. Step 1: Understand the purpose of left_join

   left_join keeps all rows from the first (left) table regardless of matches.

2. Step 2: Understand how matching rows are added

   It adds columns from the second (right) table only where keys match, filling with NA if no match.

3. Final Answer:

   Keeps all rows from the first table and adds matching rows from the second table. -> Option D

4. Quick Check:

   left_join = all left rows + matching right rows [OK]

Hint: Remember: left_join keeps all from left, adds matches [OK]

Common Mistakes:

• Confusing left_join with inner_join
• Thinking left_join removes unmatched rows
• Mixing up which table is 'left' or 'right'

2. Which of the following is the correct syntax to perform an inner join of two data frames df1 and df2 by the column id in R?

easy

A. inner_join(df1, df2, on = "id")

B. innerjoin(df1, df2, on = "id")

C. inner_join(df1, df2, by = "id")

D. innerjoin(df1, df2, by = "id")

Solution

1. Step 1: Identify correct function name and parameters

   The function is inner_join from dplyr, and it uses by to specify join columns.

2. Step 2: Check parameter names and spelling

   Correct syntax is inner_join(df1, df2, by = "id"). Other options use wrong function names or parameter names.

3. Final Answer:

   inner_join(df1, df2, by = "id") -> Option C

4. Quick Check:

   inner_join syntax uses by = "column" [OK]

Hint: Use inner_join() with by = "column" for correct syntax [OK]

Common Mistakes:

• Using 'on' instead of 'by' for join column
• Misspelling function name as innerjoin
• Confusing parameter order

3. Given these two data frames:

df1 <- data.frame(id = c(1, 2, 3), value1 = c("A", "B", "C"))
df2 <- data.frame(id = c(2, 3, 4), value2 = c("X", "Y", "Z"))

What is the result of inner_join(df1, df2, by = "id")?

medium

A. Rows with ids 2 and 3 with columns from both data frames

B. Rows with ids 1, 2, 3, 4 with all columns

C. Rows with ids 1 and 4 only

D. Rows with ids 1, 2, 3 with only columns from df1

Solution

1. Step 1: Identify matching ids in both data frames

   df1 has ids 1, 2, 3; df2 has ids 2, 3, 4. Common ids are 2 and 3.

2. Step 2: Understand inner_join output

   inner_join keeps only rows with matching ids and combines columns from both data frames for those rows.

3. Final Answer:

   Rows with ids 2 and 3 with columns from both data frames -> Option A

4. Quick Check:

   inner_join = only matching rows [OK]

Hint: inner_join keeps only rows with matching keys [OK]

Common Mistakes:

• Including unmatched rows in inner_join result
• Confusing inner_join with left_join
• Ignoring columns from second data frame

4. You run this code:

left_join(df1, df2, by = "id")

but get an error: Error: object 'df2' not found. What is the likely cause?

medium

A. The data frame df2 was not created or loaded before the join.

B. The by argument is misspelled.

C. left_join cannot join on column named 'id'.

D. You need to use inner_join instead of left_join.

Solution

1. Step 1: Analyze the error message

   The error says df2 is not found, meaning R cannot find the object named df2.

2. Step 2: Identify cause of missing object

   This usually means df2 was not created, loaded, or is misspelled before calling left_join.

3. Final Answer:

   The data frame df2 was not created or loaded before the join. -> Option A

4. Quick Check:

   Missing data frame causes object not found error [OK]

Hint: Check if all data frames exist before joining [OK]

Common Mistakes:

• Assuming join syntax error causes object not found
• Ignoring typo in data frame names
• Thinking join functions require special packages loaded

5. You have two data frames:

students <- data.frame(student_id = c(1, 2, 3, 4), name = c("Anna", "Ben", "Cara", "Dan"))
scores <- data.frame(student_id = c(2, 3, 5), score = c(88, 92, 75))

You want a table that shows all students with their scores if available, and NA if no score exists. Which join function and code should you use?

hard

A. inner_join(students, scores, by = "student_id")

B. left_join(students, scores, by = "student_id")

C. right_join(students, scores, by = "student_id")

D. full_join(students, scores, by = "student_id")

Solution

1. Step 1: Understand the goal

   You want all students listed, even if they don't have a score, with scores added where available.

2. Step 2: Choose the correct join

   left_join keeps all rows from the first table (students) and adds matching scores, filling with NA if no match.

3. Final Answer:

   left_join(students, scores, by = "student_id") -> Option B

4. Quick Check:

   left_join keeps all left rows, adds matches, fills NA [OK]

Hint: Use left_join to keep all from first table with matches [OK]

Common Mistakes:

• Using inner_join which drops students without scores
• Using right_join which keeps all scores but drops some students
• Using full_join which adds extra rows not needed