filter() for row selection in R Programming - Time & Space Complexity

Time Complexity: filter() for row selection

O(n)

Understanding Time Complexity

When we use filter() to select rows in R, it checks each row to see if it meets the condition.

We want to know how the time it takes grows as the number of rows grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

library(dplyr)
data <- data.frame(
  id = 1:1000,
  score = sample(1:100, 1000, replace = TRUE)
)

filtered_data <- filter(data, score > 50)

This code creates a data frame with 1000 rows and selects rows where the score is greater than 50.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each row's score against the condition score > 50.
• How many times: Once for every row in the data frame.

How Execution Grows With Input

As the number of rows increases, the number of checks grows at the same rate.

Input Size (n)	Approx. Operations
10	10 checks
100	100 checks
1000	1000 checks

Pattern observation: The work grows directly with the number of rows.

Final Time Complexity

Time Complexity: O(n)

This means the time to filter rows grows in a straight line as the number of rows grows.

Common Mistake

[X] Wrong: "Filtering rows is instant no matter how many rows there are."

[OK] Correct: Each row must be checked, so more rows mean more work and more time.

Interview Connect

Understanding how filtering scales helps you write efficient data code and explain your choices clearly.

Self-Check

"What if we filter using multiple conditions combined with AND or OR? How would the time complexity change?"