String Basics and Memory Representation in DSA Python - Time & Space Complexity

Time Complexity: String Basics and Memory Representation

O(n²)

Understanding Time Complexity

We want to understand how the time to work with strings changes as the string gets longer.

Specifically, how operations like reading or copying a string take more time with bigger strings.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code copies each character from one string to another by adding characters one by one.

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 original string (n times).

How Execution Grows With Input

As the string gets longer, the time to copy it grows faster than just the length.

Input Size (n)	Approx. Operations
10	About 55 operations
100	About 5050 operations
1000	About 500500 operations

Pattern observation: The operations grow roughly with the square of the string length.

Final Time Complexity

Time Complexity: O(n²)

This means copying a string by adding characters one by one takes much more time as the string grows, roughly the square of its length.

Common Mistake

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

[OK] Correct: Each time you add a character, a new string is created copying all previous characters, so the total work adds up to much more than just n.

Interview Connect

Understanding how string operations cost time helps you write efficient 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?"