Common string transformations in Python - Time & Space Complexity

Time Complexity: Common string transformations

O(n)

Understanding Time Complexity

When we change strings by making them uppercase, lowercase, or replacing parts, the time it takes depends on the string's length.

We want to know how the work grows as the string gets longer.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

text = "Hello World"
upper_text = text.upper()
lower_text = text.lower()
replaced_text = text.replace('o', '0')
trimmed_text = text.strip()
    

This code changes a string to uppercase, lowercase, replaces characters, and removes spaces from the ends.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Going through each character in the string to change or check it.
• How many times: Once for each character in the string for each transformation.

How Execution Grows With Input

As the string gets longer, the time to change it grows in a straight line with the number of characters.

Input Size (n)	Approx. Operations
10	About 10 operations per transformation
100	About 100 operations per transformation
1000	About 1000 operations per transformation

Pattern observation: The work grows evenly as the string length grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to do these string changes grows directly with the string length.

Common Mistake

[X] Wrong: "Changing a string's case or replacing characters is instant and does not depend on string size."

[OK] Correct: Each character must be checked or changed, so longer strings take more time.

Interview Connect

Understanding how string operations grow with size helps you write clear and efficient code, a skill valued in many coding challenges and real projects.

Self-Check

"What if we used a method that only changes the first character of the string? How would the time complexity change?"