Substring extraction (${var:offset:length}) in Bash Scripting - Time & Space Complexity

Time Complexity: Substring extraction (${var:offset:length})

O(k)

Understanding Time Complexity

We want to understand how the time it takes to extract a substring changes as the size of the substring or the original string changes.

How does the work grow when we ask for longer parts of the string?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

string="Hello, world!"
sub1=${string:0:5}
sub2=${string:7:5}
sub3=${string:0:10}

# Extract different parts of the string

This code extracts parts of a string using the substring syntax: starting at an offset and taking a certain length.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Copying characters from the original string to create the substring.
• How many times: Once for each character in the substring length.

How Execution Grows With Input

Extracting a substring means copying each character one by one for the requested length.

Input Size (substring length)	Approx. Operations (character copies)
10	10
100	100
1000	1000

Pattern observation: The work grows directly with the length of the substring requested.

Final Time Complexity

Time Complexity: O(k)

This means the time to extract a substring grows linearly with the length of the substring, not the whole string.

Common Mistake

[X] Wrong: "Extracting a substring always takes time proportional to the whole string length."

[OK] Correct: The operation only copies the requested part, so time depends on substring length, not the full string size.

Interview Connect

Knowing how substring extraction scales helps you write efficient scripts and answer questions about string handling in interviews confidently.

Self-Check

"What if we extract multiple substrings in a loop from a very long string? How would the time complexity change?"