Why strings are mutable in Ruby - Performance Analysis

Time Complexity: Why strings are mutable in Ruby

O(n)

Understanding Time Complexity

We want to understand how changing strings in Ruby affects the time it takes to run code.

Specifically, we ask: How does the ability to change strings impact the number of steps the program takes?

Scenario Under Consideration

Analyze the time complexity of modifying a string repeatedly.

str = "hello"
10.times do |i|
  str << "!"
end
puts str
    

This code adds an exclamation mark to the string 10 times, changing the string each time.

Identify Repeating Operations

Look for repeated actions that take time.

• Primary operation: Adding a character to the string with << inside a loop.
• How many times: 10 times, once per loop cycle.

How Execution Grows With Input

As we add more characters, the work grows with the number of additions.

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

Pattern observation: The time grows roughly in direct proportion to how many times we add to the string.

Final Time Complexity

Time Complexity: O(n)

This means if you add to the string n times, the time it takes grows roughly the same as n.

Common Mistake

[X] Wrong: "Adding to a string always takes the same time no matter how long it is."

[OK] Correct: Actually, adding to a string can take longer if the string needs to grow its storage space, so time depends on how many times you add.

Interview Connect

Understanding how string changes affect time helps you write clear and efficient code, a skill valued in many coding challenges and real projects.

Self-Check

"What if we used string concatenation with + instead of << inside the loop? How would the time complexity change?"