Row and column indexing in R Programming - Time & Space Complexity

Time Complexity: Row and column indexing

O(k)

Understanding Time Complexity

We want to understand how the time it takes to get rows and columns from a data frame changes as the data grows.

How does the work grow when we ask for more rows or columns?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

# Create a data frame with n rows and m columns
n <- 1000
m <- 50
DF <- data.frame(matrix(1:(n*m), nrow = n, ncol = m))

# Extract a single row
row_10 <- DF[10, ]

# Extract a single column
col_5 <- DF[, 5]

# Extract multiple rows and columns
subset <- DF[1:100, 1:10]
    

This code creates a data frame and extracts rows and columns using indexing.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing elements by row and column indexes involves reading data from memory.
• How many times: For a single row or column, it reads all elements in that row or column once. For multiple rows and columns, it reads all selected elements.

How Execution Grows With Input

When you get one row, the work depends on how many columns there are. When you get one column, the work depends on how many rows there are.

Input Size (n rows, m columns)	Approx. Operations for one row	Approx. Operations for one column
10 rows, 5 columns	5 reads	10 reads
100 rows, 50 columns	50 reads	100 reads
1000 rows, 100 columns	100 reads	1000 reads

Pattern observation: The time grows linearly with the number of elements you extract, either by row or column.

Final Time Complexity

Time Complexity: O(k)

This means the time grows directly with the number of elements you select (k), whether from rows or columns.

Common Mistake

[X] Wrong: "Extracting a single row or column always takes the same time regardless of size."

[OK] Correct: The time depends on how many elements are in that row or column, so bigger rows or columns take more time.

Interview Connect

Understanding how data access time grows helps you write efficient code and explain your choices clearly in real projects or interviews.

Self-Check

"What if we extract multiple non-contiguous rows and columns using a vector of indexes? How would the time complexity change?"