Why strings are used in Python - Performance Analysis

Time Complexity: Why strings are used

O(n^2)

Understanding Time Complexity

We want to understand how using strings affects the time it takes for a program to run.

Specifically, we ask: how does the work grow when we handle longer strings?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

text = "hello"
reversed_text = ""
for char in text:
    reversed_text = char + reversed_text
print(reversed_text)

This code reverses a string by adding each character to the front of a new string.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each character in the string.
• How many times: Once for every character in the input string.

How Execution Grows With Input

As the string gets longer, the loop runs more times, and each time it creates a new string by adding characters.

Input Size (n)	Approx. Operations
5	About 15 operations (adding characters repeatedly)
10	About 55 operations
100	About 5,050 operations

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

Final Time Complexity

Time Complexity: O(n2)

This means if the string doubles in length, the work more than doubles, growing roughly with the square of the string size.

Common Mistake

[X] Wrong: "Adding characters to a string inside a loop is always fast and simple, so it takes time proportional to the string length."

[OK] Correct: Each time you add to a string, a new string is made copying all characters so far, making the total work grow much faster than just the length.

Interview Connect

Understanding how string operations grow with input size helps you write better code and explain your choices clearly in interviews.

Self-Check

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