String creation in Java - Time & Space Complexity

schedule

Time Complexity: String creation

O(n²)

menu_book

Understanding Time Complexity

We want to see how the time needed to create strings changes as we make bigger or more strings.

How does the work grow when we build strings in different ways?

code_blocks

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public class StringCreation {
    public static void main(String[] args) {
        String s = "";
        for (int i = 0; i < 1000; i++) {
            s += i;
        }
    }
}
    

This code builds a string by adding numbers one by one in a loop.

repeat

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding numbers to the string inside the loop.
• How many times: The loop runs 1000 times, and each time it creates a new string by copying the old one plus the new number.

search_insights

How Execution Grows With Input

Each time we add to the string, the program copies the whole string so far, which takes longer as the string grows.

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; it grows roughly like the square of the input.

cards_stack

Final Time Complexity

Time Complexity: O(n²)

This means the time needed grows roughly with the square of how many times we add to the string.

chat_error

Common Mistake

[X] Wrong: "Adding to a string in a loop always takes the same time as the number of loop runs."

[OK] Correct: Each addition copies the whole string so far, so the work grows more than just the loop count.

business_center

Interview Connect

Understanding how string creation time grows helps you write faster code and explain your choices clearly in interviews.

psychology_alt

Self-Check

"What if we used a StringBuilder instead of adding strings directly? How would the time complexity change?"