C Sharp (C#)programming~5 mins

String type and immutability in C Sharp (C#) - Time & Space Complexity

Choose your learning style9 modes available

Time Complexity: String type and immutability

O(n²)

Understanding Time Complexity

When working with strings in C#, it's important to understand how their immutability affects performance.

We want to see how the time to process strings changes as the string size grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.


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

This code builds a string by adding the character 'a' one by one in a loop.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

Primary operation: Adding a character to the string inside the loop.
How many times: The loop runs n times, and each addition creates a new string.

How Execution Grows With Input

Each time we add a character, a new string is created by copying the old string plus the new character.

Pattern observation: The work grows roughly like the square of n because each addition copies all previous characters.

Final Time Complexity

Time Complexity: O(n²)

This means the time to build the string grows much faster than the string length, making it slower for large n.

Common Mistake

[X] Wrong: "Adding characters in a loop to a string is fast and takes time proportional to n."

[OK] Correct: Because strings are immutable, each addition copies the whole string, causing time to grow much faster than n.

Interview Connect

Understanding string immutability and its impact on performance shows you know how data structures affect code speed, a key skill in programming.

Self-Check

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