String concatenation and repetition in Python - Time & Space Complexity

Time Complexity: String concatenation and repetition

O(n² * m)

Understanding Time Complexity

We want to understand how the time needed to join or repeat strings changes as the strings get longer or the repetition count grows.

How does the work grow when we add more pieces or repeat more times?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def repeat_and_concat(s, n):
    result = ""
    for _ in range(n):
        result += s
    return result

This code repeats a string s n times by adding it to a result string in a loop.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding the string s to result inside the loop.
• How many times: The loop runs n times, each time concatenating strings.

How Execution Grows With Input

Each time we add s to result, the whole result string is copied to make space for the new addition. So the work grows more than just n times.

Input Size (n)	Approx. Operations
10	About 55 times length of s
100	About 5050 times length of s
1000	About 500500 times length of s

Pattern observation: The work grows roughly like the square of n, because each addition copies a longer string.

Final Time Complexity

Time Complexity: O(n² * m) where m is the length of s

This means the time needed grows roughly with the square of the number of repetitions times the length of the string, making it slower as n gets bigger.

Common Mistake

[X] Wrong: "Adding a string n times in a loop is just O(n) because the loop runs n times."

[OK] Correct: Each addition copies the whole growing string, so the work adds up more than just n times. The string gets longer each time, making concatenation slower.

Interview Connect

Understanding how string operations grow helps you write faster code and explain your choices clearly. It shows you think about how your program behaves as data grows.

Self-Check

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