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

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.

Input Size (n)	Approx. Operations
10	About 55 copies (1+2+...+10)
100	About 5,050 copies
1000	About 500,500 copies

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?

Practice

1. What does it mean that strings in C# are immutable?

easy

A. Once created, the string cannot be changed; any modification creates a new string.

B. Strings can be changed directly without creating a new string.

C. Strings are stored as numbers internally.

D. Strings can only contain letters and no numbers.

Solution

1. Step 1: Understand immutability concept

   Immutability means the value cannot be changed after creation.

2. Step 2: Apply to strings in C#

   In C#, strings cannot be changed once created; any change makes a new string.

3. Final Answer:

   Once created, the string cannot be changed; any modification creates a new string. -> Option A

4. Quick Check:

   String immutability = cannot change original string [OK]

Hint: Remember: strings never change, they create new copies [OK]

Common Mistakes:

• Thinking strings can be changed in place
• Confusing immutability with read-only variables
• Assuming strings only hold letters

2. Which of the following is the correct way to declare a string variable in C#?

easy

A. string name = "Alice";

B. String name = 'Alice';

C. string name = Alice;

D. String name = Alice;

Solution

1. Step 1: Check string declaration syntax

   In C#, strings use double quotes and the lowercase keyword 'string'.

2. Step 2: Identify correct syntax

   string name = "Alice"; uses lowercase 'string' and double quotes correctly.

3. Final Answer:

   string name = "Alice"; -> Option A

4. Quick Check:

   Use double quotes and string keyword [OK]

Hint: Use double quotes for strings and lowercase 'string' keyword [OK]

Common Mistakes:

• Using single quotes for strings
• Omitting quotes around text
• Confusing 'string' with 'String' casing

3. What will be the output of this C# code?

string s = "hello";
s = s.ToUpper();
Console.WriteLine(s);

medium

A. hello

B. HELLO

C. Hello

D. Error

Solution

1. Step 1: Understand ToUpper() method

   ToUpper() returns a new string with all letters uppercase.

2. Step 2: Assign new string to s and print

   Variable s is updated to the uppercase string, so printing s shows "HELLO".

3. Final Answer:

   HELLO -> Option B

4. Quick Check:

   ToUpper() creates uppercase string [OK]

Hint: ToUpper() returns new uppercase string; assign it to variable [OK]

Common Mistakes:

• Assuming original string changes without assignment
• Expecting lowercase output
• Thinking ToUpper() modifies string in place

4. Identify the error in this code snippet:

string s = "test";
s[0] = 'T';
Console.WriteLine(s);

medium

A. Strings cannot be indexed in C#.

B. Console.WriteLine requires parentheses.

C. Cannot assign to string index because strings are immutable.

D. Missing semicolon after string declaration.

Solution

1. Step 1: Check string indexing and assignment

   Strings can be indexed to read characters but cannot assign to indexes.

2. Step 2: Understand immutability prevents changing characters

   Because strings are immutable, s[0] = 'T' causes a compile error.

3. Final Answer:

   Cannot assign to string index because strings are immutable. -> Option C

4. Quick Check:

   Strings immutable = no character assignment [OK]

Hint: You can read chars by index but cannot assign to them [OK]

Common Mistakes:

• Trying to change string characters by index
• Confusing indexing with arrays
• Ignoring immutability rules

5. Given this code, what will be the output?

string original = "cat";
string changed = original.Replace('c', 'b');
Console.WriteLine(original);
Console.WriteLine(changed);

hard

A. Error at Replace method

B. bat
bat

C. cat
cat

D. cat
bat

Solution

1. Step 1: Understand Replace method on strings

   Replace returns a new string with specified characters replaced; original string stays unchanged.

2. Step 2: Analyze output of both Console.WriteLine calls

   original prints "cat" unchanged; changed prints "bat" with 'c' replaced by 'b'.

3. Final Answer:

   cat bat -> Option D

4. Quick Check:

   Replace returns new string, original unchanged [OK]

Hint: Replace returns new string; original string stays same [OK]

Common Mistakes:

• Assuming original string changes after Replace
• Expecting both outputs to be same
• Thinking Replace modifies string in place