String creation and literal types in C Sharp (C#) - Time & Space Complexity

Time Complexity: String creation and literal types

O(n²)

Understanding Time Complexity

When we create strings in C#, the way we do it affects how long it takes. We want to understand how the time to create strings grows as we work with more or bigger strings.

How does the method of creating strings impact the time needed as the input size changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

string result = "";
for (int i = 0; i < n; i++)
{
    result += i.ToString();
}
return result;
    

This code builds a string by adding the string form of each number from 0 up to n-1.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The loop runs n times, and each time it appends to the string.
• How many times: The loop repeats n times, and each append creates a new string internally.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
10	About 55 string operations (adding lengths 1 to 10)
100	About 5,050 string operations (adding lengths 1 to 100)
1000	About 500,500 string operations (adding lengths 1 to 1000)

Pattern observation: Each new string is longer, so the total work grows much faster than n; it grows roughly like the sum of numbers from 1 to n.

Final Time Complexity

Time Complexity: O(n²)

This means the time to build the string grows roughly with the square of the number of items added.

Common Mistake

[X] Wrong: "Appending strings in a loop always takes linear time."

[OK] Correct: Each append creates a new string copying all previous content, so the total time adds up much more than just n times.

Interview Connect

Understanding how string creation time grows helps you write efficient code and explain your choices clearly in interviews. It shows you know how small details affect performance.

Self-Check

"What if we used a StringBuilder instead of string concatenation? How would the time complexity change?"