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?"

Practice

1. What does the tr command do in bash scripting?

easy

A. It transforms or deletes characters from input text streams.

B. It compiles bash scripts into executables.

C. It lists files in a directory.

D. It runs commands in the background.

Solution

1. Step 1: Understand the purpose of tr

   The tr command is used to translate or delete characters from input text streams.

2. Step 2: Compare with other options

   Options B, C, and D describe unrelated commands or functions in bash.

3. Final Answer:

   It transforms or deletes characters from input text streams. -> Option A

4. Quick Check:

   tr = transform/delete characters [OK]

Hint: Remember: tr means translate characters [OK]

Common Mistakes:

• Confusing tr with file listing commands like ls
• Thinking tr compiles scripts
• Assuming tr runs commands in background

2. Which of the following is the correct syntax to convert lowercase letters to uppercase using tr?

easy

A. echo "hello" | tr 'A-Z' '0-9'

B. echo "hello" | tr 'a-z' 'A-Z'

C. echo "hello" | tr '0-9' 'A-Z'

D. echo "hello" | tr 'A-Z' 'a-z'

Solution

1. Step 1: Identify the correct character ranges for case conversion

   To convert lowercase to uppercase, use 'a-z' as source and 'A-Z' as target.

2. Step 2: Check the syntax correctness

   echo "hello" | tr 'a-z' 'A-Z' correctly uses tr 'a-z' 'A-Z'. Other options either reverse case or use wrong ranges.

3. Final Answer:

   echo "hello" | tr 'a-z' 'A-Z' -> Option B

4. Quick Check:

   Lowercase to uppercase = echo "hello" | tr 'a-z' 'A-Z' [OK]

Hint: Use 'a-z' then 'A-Z' to uppercase letters [OK]

Common Mistakes:

• Swapping source and target ranges
• Using digits instead of letters
• Mixing uppercase and lowercase incorrectly

3. What is the output of this command?

echo "Hello World 123" | tr -d '0-9'

medium

A. Hello World 123

B. HelloWorld123

C. HelloWorld

D. Hello World

Solution

1. Step 1: Understand the -d option in tr

   The -d option deletes characters matching the set given, here digits '0-9'.

2. Step 2: Apply deletion to the input string

   All digits '1', '2', '3' are removed, leaving "Hello World " with spaces intact.

3. Final Answer:

   Hello World -> Option D

4. Quick Check:

   Digits deleted = "Hello World " [OK]

Hint: Use -d to delete characters, here digits removed [OK]

Common Mistakes:

• Expecting digits to be replaced, not deleted
• Removing spaces accidentally
• Confusing -d with character translation

4. Identify the error in this command:

echo "abc123" | tr 'a-z' 'A-Z' -d '0-9'

medium

A. The command will convert letters but ignore digits.

B. The order of options is wrong; -d must come before sets.

C. You cannot combine translation and deletion in one tr command.

D. The syntax is correct and will work as expected.

Solution

1. Step 1: Understand tr option usage

   tr does not support combining translation and deletion in one command; they are separate operations.

2. Step 2: Analyze the command

   The command tries to translate and delete simultaneously, which is invalid syntax.

3. Final Answer:

   You cannot combine translation and deletion in one tr command. -> Option C

4. Quick Check:

   Translation + deletion together = invalid [OK]

Hint: tr does either translate OR delete, not both at once [OK]

Common Mistakes:

• Trying to chain translate and delete in one tr call
• Assuming option order fixes the problem
• Expecting partial command success

5. You want to replace all vowels in a string with the character '*', but keep other characters unchanged. Which command achieves this?

hard

A. echo "banana" | tr 'aeiou' '*'

B. echo "banana" | tr 'aeiou' 'AEIOU'

C. echo "banana" | tr -d 'aeiou'

D. echo "banana" | tr 'aeiou' 'ABCDE'

Solution

1. Step 1: Understand character replacement with tr

   To replace vowels with '*', map all vowels to a single character '*'.

2. Step 2: Analyze each option

   echo "banana" | tr 'aeiou' '*' replaces each vowel with '*'. echo "banana" | tr 'aeiou' 'AEIOU' changes vowels to uppercase vowels. echo "banana" | tr -d 'aeiou' deletes vowels. echo "banana" | tr 'aeiou' 'ABCDE' replaces vowels with A,B,C,D,E respectively.

3. Final Answer:

   echo "banana" | tr 'aeiou' '*' -> Option A

4. Quick Check:

   Vowels replaced by '*' = echo "banana" | tr 'aeiou' '*' [OK]

Hint: Map vowels to '*' with single char target in tr [OK]

Common Mistakes:

• Using a target set like 'ABCDE' instead of '*'
• Deleting vowels instead of replacing
• Replacing vowels with uppercase instead of '*'