Reduce/inject for accumulation in Ruby - Time & Space Complexity

Time Complexity: Reduce/inject for accumulation

O(n)

Understanding Time Complexity

We want to understand how the time to add up values using reduce or inject changes as the list gets bigger.

How does the number of steps grow when we accumulate many items?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

numbers = [1, 2, 3, 4, 5]
sum = numbers.reduce(0) do |acc, num|
  acc + num
end
puts sum

This code adds all numbers in the array using reduce, starting from zero.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding each number to the accumulator inside the reduce loop.
• How many times: Once for each item in the array.

How Execution Grows With Input

Each new number means one more addition step.

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

Pattern observation: The steps grow directly with the number of items.

Final Time Complexity

Time Complexity: O(n)

This means the time to add all numbers grows in a straight line as the list gets bigger.

Common Mistake

[X] Wrong: "Reduce runs in constant time no matter how many items there are."

[OK] Correct: Reduce must visit each item once, so time grows with the list size.

Interview Connect

Understanding how reduce works helps you explain how simple loops add up values efficiently in real tasks.

Self-Check

"What if we used reduce to multiply all numbers instead of adding? How would the time complexity change?"