sub and gsub in R Programming - Time & Space Complexity

Time Complexity: sub and gsub

O(n)

Understanding Time Complexity

We want to understand how the time it takes to replace text grows when using sub and gsub in R.

How does the work change as the text gets longer or has more matches?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

text <- c("apple apple", "banana apple", "apple banana apple")
result_sub <- sub("apple", "orange", text)
result_gsub <- gsub("apple", "orange", text)

This code replaces the first occurrence of "apple" with "orange" using sub, and all occurrences using gsub, in a vector of strings.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each string to find matches of the pattern.
• How many times: For sub, scanning stops after the first match per string; for gsub, scanning continues through the entire string to find all matches.

How Execution Grows With Input

As the length of each string or the number of strings grows, the work increases.

Input Size (n)	Approx. Operations
10 (short strings)	About 10 scans for sub, 10 full scans for gsub
100 (longer strings)	About 100 scans for sub, 100 full scans for gsub
1000 (many long strings)	About 1000 scans for sub, 1000 full scans for gsub

Pattern observation: The time grows roughly in direct proportion to the total length of all strings. gsub does more work per string because it finds all matches, not just the first.

Final Time Complexity

Time Complexity: O(n)

This means the time to replace text grows linearly with the total size of the input strings.

Common Mistake

[X] Wrong: "sub and gsub always take the same time because they do similar replacements."

[OK] Correct: sub stops after the first match in each string, so it often does less work than gsub, which finds and replaces all matches.

Interview Connect

Understanding how string replacement scales helps you write efficient code when working with text data, a common task in many projects.

Self-Check

"What if we changed the pattern to a more complex regular expression? How would the time complexity change?"

Practice

1. What is the main difference between sub and gsub in R?

easy

A. sub works only with numbers, gsub works only with text.

B. sub replaces all matches, gsub replaces only the first match.

C. sub replaces only the first match, gsub replaces all matches.

D. sub modifies the original string, gsub returns a new string.

Solution

1. Step 1: Understand sub behavior

   sub replaces only the first occurrence of the pattern in the string.

2. Step 2: Understand gsub behavior

   gsub replaces all occurrences of the pattern in the string.

3. Final Answer:

   sub replaces only the first match, gsub replaces all matches. -> Option C

4. Quick Check:

   sub = first match, gsub = all matches [OK]

Hint: Remember: sub = first, gsub = global (all) [OK]

Common Mistakes:

• Confusing which function replaces all matches
• Thinking sub modifies original string in place
• Assuming gsub only replaces first match

2. Which of the following is the correct syntax to replace the first occurrence of "cat" with "dog" in the string "cat and cat" using sub?

easy

A. sub("cat", "dog", "cat and cat")

B. sub("dog", "cat", "cat and cat")

C. gsub("cat", "dog", "cat and cat")

D. replace("cat", "dog", "cat and cat")

Solution

1. Step 1: Identify correct function and parameters

   sub takes pattern, replacement, and the string in that order.

2. Step 2: Check the parameters match the question

   We want to replace "cat" with "dog" in "cat and cat" using sub.

3. Final Answer:

   sub("cat", "dog", "cat and cat") -> Option A

4. Quick Check:

   Correct syntax with sub and parameters [OK]

Hint: sub(pattern, replacement, string) is the order [OK]

Common Mistakes:

• Swapping pattern and replacement arguments
• Using gsub instead of sub for first occurrence
• Using a non-existent function like replace

3. What will be the output of the following R code?

text <- "apple apple apple"
result <- sub("apple", "orange", text)
print(result)

medium

A. "orange orange orange"

B. "orange apple apple"

C. "apple orange apple"

D. "apple apple orange"

Solution

1. Step 1: Understand sub replaces first match only

   The first "apple" in the string is replaced by "orange".

2. Step 2: Apply replacement to the string

   Result becomes "orange apple apple" because only the first "apple" changes.

3. Final Answer:

   "orange apple apple" -> Option B

4. Quick Check:

   sub replaces first match only [OK]

Hint: sub changes only first match, not all [OK]

Common Mistakes:

• Thinking sub replaces all matches
• Confusing sub with gsub
• Expecting all words to change

4. The following code is intended to replace all spaces with underscores in the string "hello world example" but does not work as expected. What is the error?

text <- "hello world example"
new_text <- sub(" ", "_", text)
print(new_text)

medium

A. The print statement is incorrect syntax.

B. The pattern " " is invalid, use "\\s" instead.

C. The replacement string should be "-" not "_".

D. sub replaces only the first space, use gsub to replace all spaces.

Solution

1. Step 1: Identify function behavior

   sub replaces only the first match, so only the first space is replaced.

2. Step 2: Suggest correct function for all replacements

   To replace all spaces, gsub should be used instead of sub.

3. Final Answer:

   sub replaces only the first space, use gsub to replace all spaces. -> Option D

4. Quick Check:

   Use gsub for all matches, sub for first only [OK]

Hint: Use gsub to replace all matches, not sub [OK]

Common Mistakes:

• Using sub when gsub is needed
• Thinking space pattern is invalid
• Changing replacement character unnecessarily

5. You have a vector of strings: c("cat123", "dog456", "bird789"). You want to remove all digits from each string. Which R code correctly does this using gsub?

hard

A. gsub("[0-9]", "", c("cat123", "dog456", "bird789"))

B. sub("[0-9]", "", c("cat123", "dog456", "bird789"))

C. gsub("[^0-9]+", "", c("cat123", "dog456", "bird789"))

D. sub("\\d", "", c("cat123", "dog456", "bird789"))

Solution

1. Step 1: Identify pattern to remove digits

   The pattern "[0-9]" matches any single digit; "\\d+" matches one or more digits.

2. Step 2: Choose function to replace all digits

   Use gsub to replace all digit occurrences, not just the first.

3. Step 3: Check options

   gsub("[0-9]", "", c("cat123", "dog456", "bird789")) uses gsub with "[0-9]" which removes all digits correctly.

4. Final Answer:

   gsub("[0-9]", "", c("cat123", "dog456", "bird789")) -> Option A

5. Quick Check:

   gsub + digit pattern removes all digits [OK]

Hint: Use gsub with digit pattern to remove all digits [OK]

Common Mistakes:

• Using sub instead of gsub, removing only first digit
• Incorrect regex pattern for digits
• Confusing escape sequences in regex