String immutability in Python - Time & Space Complexity

Time Complexity: String immutability

O(n^2)

Understanding Time Complexity

When working with strings in Python, it's important to know how changes affect performance.

We want to see how the time to modify a string grows as the string gets longer.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

text = "hello"
new_text = ""
for char in text:
    new_text += char.upper()
print(new_text)

This code creates a new string by changing each character to uppercase and adding it to a new string.

Identify Repeating Operations

• Primary operation: Looping through each character and adding to a new string.
• How many times: Once for each character in the original string.

How Execution Grows With Input

Each time we add a character, Python creates a new string by copying the old one plus the new character.

Input Size (n)	Approx. Operations
10	About 55 copies (1+2+...+10)
100	About 5050 copies
1000	About 500,500 copies

Pattern observation: The work grows much faster than the input size because each addition copies the whole string so far.

Final Time Complexity

Time Complexity: O(n2)

This means the time to build the new string grows roughly with the square of the string length.

Common Mistake

[X] Wrong: "Adding characters to a string inside a loop is fast and scales linearly."

[OK] Correct: Because strings are immutable, each addition makes a new string copying all previous characters, causing much more work as the string grows.

Interview Connect

Understanding string immutability helps you explain why some string operations can be slow and how to write efficient code.

Self-Check

What if we used a list to collect characters and joined them at the end? How would the time complexity change?