String type and immutability in Kotlin - Time & Space Complexity

Time Complexity: String type and immutability

O(n²)

Understanding Time Complexity

We want to understand how working with strings affects the time it takes for a program to run.

Specifically, how does changing or combining strings grow in cost as the strings get bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fun buildString(n: Int): String {
    var result = ""
    for (i in 1..n) {
        result += "a"
    }
    return result
}

This code creates a string by adding the letter "a" one by one, n times.

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, each time creating a new string.

How Execution Grows With Input

Each time we add a character, the program copies the whole string so far and adds one more 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 much faster than n; it grows roughly like the square of n.

Final Time Complexity

Time Complexity: O(n²)

This means the time to build the string grows very quickly as the string gets longer, because each addition copies the whole string again.

Common Mistake

[X] Wrong: "Adding one character to a string inside a loop takes the same time no matter how long the string is."

[OK] Correct: Strings are immutable, so each addition makes a new string by copying all characters, which takes more time as the string grows.

Interview Connect

Understanding how string operations grow helps you write code that runs faster and avoids surprises in real projects.

Self-Check

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