Special operators (%in%, %*%) in R Programming - Time & Space Complexity

Time Complexity: Special operators (%in%, %*%)

O(n + m) for %in% (average), O(n * m * p) for %*%

Understanding Time Complexity

We want to understand how the time it takes to run special operators like %in% and %*% changes as the input gets bigger.

In R, %in% uses hashing for efficiency, while %*% performs standard matrix multiplication.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

x <- 1:1000
y <- sample(1:2000, 1000)

# Using %in% to check membership
result_in <- x %in% y

# Using %*% to multiply matrices
A <- matrix(1, nrow=100, ncol=200)
B <- matrix(1, nrow=200, ncol=150)
result_mult <- A %*% B

This code checks which elements of x are in y using %in%, and multiplies two matrices A and B using %*%.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation for %in%: R builds a hash table of y (O(m)), then O(1) lookups for each element in x.
• How many times for %in%: Hash build: O(m), lookups: n times (average O(1) each).
• Primary operation for %*%: Multiply and sum elements across rows of A and columns of B.
• How many times for %*%: For each of n rows and p columns, sum over m elements (each a multiply-add).

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n, assume m≈n, p≈n)	Approx. Operations for %in%	Approx. Operations for %*%
10	~20 (10+10)	10 * 10 * 10 = 1,000 multiplications
100	~200 (100+100)	100 * 200 * 150 = 3,000,000 multiplications
1000	~2000 (1000+1000)	1000 * 200 * 150 = 30,000,000 multiplications

Pattern observation: %in% grows linearly with vector sizes (thanks to hashing), while %*% grows by multiplying the matrix dimensions.

Final Time Complexity

Time Complexity for %in%: O(n + m) average case (hashing).

This means the time grows linearly with the sizes of both vectors.

Time Complexity for %*%: O(n * m * p)

This means the time grows by multiplying the number of rows (n), inner dimension (m), and columns (p) of the matrices.

Common Mistake

[X] Wrong: "%in% checks each element by scanning y linearly, so O(n * m)."

[OK] Correct: R implements %in% with a hash table for y, enabling O(1) average lookups after O(m) preprocessing.

Interview Connect

Understanding implementation details like hashing in %in% and BLAS-optimized %*% shows depth in performance analysis.

Self-Check

"What if vectors were not hashable (e.g., lists)? How would %in% complexity change?"

Practice

1. What does the %in% operator do in R?

easy

A. Calculates the sum of two vectors

B. Performs element-wise multiplication of two vectors

C. Performs matrix multiplication

D. Checks if elements of one vector are present in another vector

Solution

1. Step 1: Understand the purpose of %in%

   The %in% operator is used to check membership, meaning it tests if elements of one vector exist in another.

2. Step 2: Compare with other operations

   Other options describe arithmetic or matrix operations, which are not the function of %in%.

3. Final Answer:

   Checks if elements of one vector are present in another vector -> Option D

4. Quick Check:

   %in% = membership check [OK]

Hint: Remember: %in% means 'is in' for membership [OK]

Common Mistakes:

• Confusing %in% with arithmetic operators
• Thinking %in% does matrix multiplication
• Assuming %in% returns numeric results

2. Which of the following is the correct syntax for matrix multiplication in R?

easy

A. A * B

B. A %*% B

C. A %in% B

D. A + B

Solution

1. Step 1: Identify matrix multiplication operator

   In R, matrix multiplication is done using %*%, so A %*% B is correct syntax.

2. Step 2: Differentiate from other operators

   * is element-wise multiplication, %in% is membership, and + is addition.

3. Final Answer:

   A %*% B -> Option B

4. Quick Check:

   Matrix multiply = %*% [OK]

Hint: Use %*% for matrix multiply, * for element-wise [OK]

Common Mistakes:

• Using * instead of %*% for matrix multiplication
• Confusing %in% with multiplication
• Using + for multiplication

3. What is the output of the following R code?

x <- c(3, 1, 5)
y <- c(3, 4, 5, 6)
x %in% y

medium

A. [TRUE, FALSE, TRUE]

B. [FALSE, TRUE, FALSE]

C. [TRUE, TRUE, TRUE]

D. [FALSE, FALSE, FALSE]

Solution

1. Step 1: Check each element of x in y

   3 is in y, so TRUE; 1 is not in y, so FALSE; 5 is in y, TRUE.

2. Step 2: Form the logical vector

   The result is [TRUE, FALSE, TRUE].

3. Final Answer:

   [TRUE, FALSE, TRUE] -> Option A

4. Quick Check:

   %in% returns logical vector [OK]

Hint: Check each element presence one by one [OK]

Common Mistakes:

• Mixing order of TRUE/FALSE in output
• Assuming %in% returns indices
• Confusing %in% with element-wise comparison

4. Identify the error in the following R code:

A <- matrix(c(1,2,3,4), nrow=2)
B <- matrix(c(5,6,7,8), nrow=2)
C <- A *%* B

medium

A. Matrices A and B have incompatible dimensions

B. Missing library for matrix multiplication

C. Incorrect operator *%* used for matrix multiplication

D. Matrix A is not defined properly

Solution

1. Step 1: Check operator syntax

   The operator *%* is invalid in R; correct operator is %*%.

2. Step 2: Verify matrix dimensions and definitions

   Both matrices are 2x2, so dimensions are compatible and matrices are defined correctly.

3. Final Answer:

   Incorrect operator *%* used for matrix multiplication -> Option C

4. Quick Check:

   Matrix multiply operator is %*% [OK]

Hint: Use %*% exactly for matrix multiplication [OK]

Common Mistakes:

• Typing operators in wrong order
• Assuming *%* is valid
• Confusing element-wise * with matrix multiply

5. Given two matrices:

M1 <- matrix(c(1, 0, 2, 3), nrow=2)
M2 <- matrix(c(4, 1, 0, 2), nrow=2)

Which R expression correctly computes the matrix product and then checks if the number 5 is in the resulting matrix?

hard

A. 5 %in% (M1 %*% M2)

B. M1 *%*% M2 %in% 5

C. M1 %in% 5 %*% M2

D. M1 %*% M2 == 5

Solution

1. Step 1: Perform matrix multiplication correctly

   Use %*% to multiply M1 and M2: M1 %*% M2.

2. Step 2: Check membership of 5 in the product matrix

   Use %in% to check if 5 is present in the resulting matrix: 5 %in% (M1 %*% M2).

3. Final Answer:

   5 %in% (M1 %*% M2) -> Option A

4. Quick Check:

   Matrix multiply then membership check = 5 %in% (M1 %*% M2) [OK]

Hint: Chain %*% then %in% with parentheses [OK]

Common Mistakes:

• Using wrong operator order
• Typing *%*% instead of %*%
• Using == instead of %in% for membership