tr for character transformation in Bash Scripting - Time & Space Complexity

Time Complexity: tr for character transformation

O(n)

Understanding Time Complexity

We want to understand how the time taken by the tr command changes as the input size grows.

Specifically, how does processing more characters affect execution time?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

echo "hello world" | tr 'a-z' 'A-Z'
    

This code converts all lowercase letters in the input string to uppercase letters.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The tr command reads each character from the input and transforms it if it matches the first set.
• How many times: It processes each character exactly once, so the number of operations grows with the number of characters.

How Execution Grows With Input

As the input string gets longer, tr must check and possibly transform each character.

Input Size (n)	Approx. Operations
10	About 10 character checks and transformations
100	About 100 character checks and transformations
1000	About 1000 character checks and transformations

Pattern observation: The work grows directly with the number of characters; doubling input doubles work.

Final Time Complexity

Time Complexity: O(n)

This means the time to transform characters grows linearly with the input size.

Common Mistake

[X] Wrong: "The tr command runs in constant time no matter the input size."

[OK] Correct: Since tr processes each character, more characters mean more work, so time grows with input length.

Interview Connect

Understanding how simple commands like tr scale helps you reason about script performance and efficiency in real tasks.

Self-Check

"What if we used tr to replace multiple characters with a single character? How would the time complexity change?"