nchar and substring in R Programming - Time & Space Complexity

Time Complexity: nchar and substring

O(n)

Understanding Time Complexity

We want to understand how the time it takes to use nchar and substring changes as the size of the text grows.

How does the length of the string affect the work these functions do?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

text <- "Hello, world!"
length_text <- nchar(text)
part_text <- substring(text, 1, 5)
print(length_text)
print(part_text)

This code finds the length of a string and extracts a part of it.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Counting characters in the string for nchar, and copying characters for substring.
• How many times: Each character is checked once for nchar, and the substring copies characters once for the requested range.

How Execution Grows With Input

As the string gets longer, nchar checks more characters, and substring copies more characters if the substring length grows.

Input Size (n)	Approx. Operations
10	About 10 checks for nchar, up to 5 copies for substring
100	About 100 checks, up to 100 copies
1000	About 1000 checks, up to 1000 copies

Pattern observation: The work grows roughly in direct proportion to the string length.

Final Time Complexity

Time Complexity: O(n)

This means the time taken grows linearly with the length of the string.

Common Mistake

[X] Wrong: "nchar and substring run instantly no matter how long the string is."

[OK] Correct: Both functions must look at characters to count or copy them, so longer strings take more time.

Interview Connect

Knowing how string operations scale helps you write efficient code and explain your choices clearly in interviews.

Self-Check

"What if we used substring to extract a fixed small part regardless of string length? How would the time complexity change?"