StringBuilder and StringBuffer in Java - Time & Space Complexity

Time Complexity: StringBuilder and StringBuffer

O(n)

Understanding Time Complexity

We want to understand how fast StringBuilder and StringBuffer work when building strings.

How does the time to add characters grow as the string gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
    sb.append('a');
}
String result = sb.toString();
    

This code builds a string by adding the letter 'a' n times using StringBuilder.

Identify Repeating Operations

• Primary operation: The loop runs n times, each time appending one character.
• How many times: Exactly n times, once per loop iteration.

How Execution Grows With Input

Each append adds one character, so the work grows as the string grows.

Input Size (n)	Approx. Operations
10	About 10 appends
100	About 100 appends
1000	About 1000 appends

Pattern observation: The time grows roughly in a straight line as n increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to build the string grows directly with the number of characters added.

Common Mistake

[X] Wrong: "Appending characters takes the same time no matter how long the string is."

[OK] Correct: Sometimes the internal array needs to grow, which takes extra time, but overall it still grows linearly.

Interview Connect

Understanding how string building scales helps you write efficient code and explain your choices clearly in interviews.

Self-Check

"What if we used String concatenation (+) inside the loop instead of StringBuilder? How would the time complexity change?"

Practice

1.

Which of the following statements about StringBuilder and StringBuffer is true?

easy

A. StringBuffer is faster and not thread-safe, while StringBuilder is thread-safe but slower.

B. StringBuilder is faster but not thread-safe, while StringBuffer is thread-safe but slower.

C. Both StringBuilder and StringBuffer are thread-safe and have the same speed.

D. StringBuilder and StringBuffer cannot be used to modify strings.

Solution

1. Step 1: Understand thread safety difference

   StringBuffer is synchronized, making it thread-safe but slower.

2. Step 2: Understand performance difference

   StringBuilder is not synchronized, so it is faster but not thread-safe.

3. Final Answer:

   StringBuilder is faster but not thread-safe, while StringBuffer is thread-safe but slower. -> Option B

4. Quick Check:

   Thread safety and speed = A [OK]

Hint: Remember: Buffer is safe but slower; Builder is fast but unsafe [OK]

Common Mistakes:

• Confusing which class is thread-safe
• Thinking both have same speed
• Believing they cannot modify strings

2.

Which of the following is the correct way to create a StringBuilder object with initial content "Hello"?

easy

A. StringBuilder sb = new StringBuffer("Hello");

B. StringBuilder sb = StringBuilder("Hello");

C. StringBuilder sb = new StringBuilder(); sb.append("Hello");

D. StringBuilder sb = new StringBuilder("Hello");

Solution

1. Step 1: Check constructor syntax

   The correct way to create a StringBuilder with initial content is using new StringBuilder("Hello").

2. Step 2: Verify other options

   StringBuilder sb = StringBuilder("Hello"); misses new, StringBuilder sb = new StringBuilder(); sb.append("Hello"); is valid but not direct initialization, StringBuilder sb = new StringBuffer("Hello"); uses wrong class.

3. Final Answer:

   StringBuilder sb = new StringBuilder("Hello"); -> Option D

4. Quick Check:

   Correct constructor syntax = D [OK]

Hint: Use 'new' keyword and constructor with string inside parentheses [OK]

Common Mistakes:

• Omitting 'new' keyword
• Using StringBuffer instead of StringBuilder
• Trying to assign without constructor

3.

What is the output of the following code?

StringBuilder sb = new StringBuilder("Java");
sb.append(" Programming");
sb.replace(0, 4, "Python");
System.out.println(sb.toString());

medium

A. PythonJava Programming

B. Java Programming

C. Python Programming

D. ProgrammingPython

Solution

1. Step 1: Append " Programming" to "Java"

   After append, string becomes "Java Programming".

2. Step 2: Replace characters from index 0 to 4 with "Python"

   Characters "Java" (index 0 to 4) are replaced by "Python", resulting in "Python Programming".

3. Final Answer:

   Python Programming -> Option C

4. Quick Check:

   Append + replace result = A [OK]

Hint: Replace changes substring; append adds at end [OK]

Common Mistakes:

• Confusing replace indices
• Thinking append replaces text
• Ignoring toString() output

4.

Identify the error in the following code snippet:

StringBuffer sb = new StringBuffer("Test");
sb.insert(5, "ing");
System.out.println(sb);

medium

A. IndexOutOfBoundsException because insert index is invalid

B. NullPointerException because sb is not initialized

C. Compilation error due to wrong method name

D. No error; output is "Testing"

Solution

1. Step 1: Check insert index validity

   StringBuffer length is 4 ("Test"), but insert index is 5, which is out of bounds.

2. Step 2: Understand exception thrown

   Inserting at index greater than length throws IndexOutOfBoundsException.

3. Final Answer:

   IndexOutOfBoundsException because insert index is invalid -> Option A

4. Quick Check:

   Invalid insert index = B [OK]

Hint: Insert index must be between 0 and length inclusive [OK]

Common Mistakes:

• Assuming insert auto-corrects index
• Confusing insert with append
• Expecting no error on invalid index

5.

You want to build a thread-safe string that appends numbers 1 to 3 separated by commas, resulting in "1,2,3". Which code snippet correctly uses StringBuffer to achieve this?

1. StringBuffer sb = new StringBuffer();
   for (int i = 1; i <= 3; i++) {
       sb.append(i);
       if (i != 3) sb.append(",");
   }
   System.out.println(sb.toString());

2. StringBuffer sb = new StringBuffer();
   for (int i = 1; i <= 3; i++) {
       sb.append(i + ",");
   }
   System.out.println(sb.toString());

3. StringBuffer sb = new StringBuffer();
   sb.append("1,2,3,");
   System.out.println(sb.toString());

4. StringBuffer sb = new StringBuffer();
   for (int i = 1; i < 3; i++) {
       sb.append(i);
       sb.append(",");
   }
   System.out.println(sb.toString());

hard

A. Code snippet 1

B. Code snippet 2

C. Code snippet 3

D. Code snippet 4

Solution

1. Step 1: Analyze snippet 1

   Appends numbers 1 to 3 with commas except after last number, producing "1,2,3" correctly.

2. Step 2: Check other snippets

   Snippet 2 adds extra comma at end; snippet 3 hardcodes string but adds extra comma; snippet 4 misses last number 3.

3. Final Answer:

   Code snippet 1 -> Option A

4. Quick Check:

   Correct comma placement in loop = C [OK]

Hint: Add comma only if not last element in loop [OK]

Common Mistakes:

• Adding extra comma at end
• Missing last number in loop
• Hardcoding string without loop