Symbol type and immutability in Ruby - Time & Space Complexity

Time Complexity: Symbol type and immutability

O(n)

Understanding Time Complexity

We want to understand how using symbols affects the speed of a Ruby program.

Specifically, how does the immutability of symbols impact repeated operations?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

1000.times do |i|
  sym = :example
  str = "example"
  sym.object_id
  str.object_id
end
    

This code uses a symbol and a string repeatedly, then checks their object IDs.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop runs 1000 times, accessing symbol and string objects.
• How many times: 1000 times for each operation inside the loop.

How Execution Grows With Input

Each loop iteration does a fixed number of steps, but creating strings is slower than using symbols.

Input Size (n)	Approx. Operations
10	10 symbol and string lookups
100	100 symbol and string lookups
1000	1000 symbol and string lookups

Pattern observation: The number of operations grows directly with the number of iterations.

Final Time Complexity

Time Complexity: O(n)

This means the time grows linearly as the number of loop runs increases.

Common Mistake

[X] Wrong: "Symbols are slow because they are created every time like strings."

[OK] Correct: Symbols are created once and reused, so accessing them is faster and uses less memory.

Interview Connect

Understanding how symbols work helps you write faster Ruby code and shows you know how data types affect performance.

Self-Check

"What if we replaced the symbol with a string literal inside the loop? How would the time complexity change?"