String creation and representation in Python - Time & Space Complexity

Time Complexity: String creation and representation

O(n^2)

Understanding Time Complexity

When we create and represent strings in Python, it is helpful to know how the time needed changes as the string gets longer.

We want to understand how the work grows when making or copying strings of different sizes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

text = ""
for char in input_string:
    text += char

This code builds a new string by adding one character at a time from an existing string.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding one character to the string inside the loop.
• How many times: Once for each character in the input string.

How Execution Grows With Input

Each time we add a character, Python creates a new string by copying the old one and adding 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 needed grows roughly with the square of the string length, making it slower for long strings.

Common Mistake

[X] Wrong: "Adding characters one by one to a string is fast and takes time proportional to the string length."

[OK] Correct: Each addition copies the entire string so far, causing the total time to grow much faster than just the length.

Interview Connect

Understanding how string building works helps you write efficient code and explain your choices clearly in real projects or interviews.

Self-Check

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