Until loop in Ruby - Time & Space Complexity

Time Complexity: Until loop

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run an until loop changes as the input grows.

Specifically, how many times does the loop run before it stops?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

count = 0
until count == n
  puts count
  count += 1
end

This code prints numbers from 0 up to n-1 using an until loop that stops when count reaches n.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The until loop runs repeatedly.
• How many times: It runs once for each number from 0 up to n-1, so n times.

How Execution Grows With Input

As n gets bigger, the loop runs more times, directly matching n.

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

Pattern observation: The number of operations grows in a straight line with n.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the loop grows directly in proportion to the input size n.

Common Mistake

[X] Wrong: "The until loop runs only once or a fixed number of times regardless of n."

[OK] Correct: The loop runs until count equals n, so it depends on n and grows as n grows.

Interview Connect

Understanding how loops grow with input size helps you explain your code clearly and shows you can think about efficiency.

Self-Check

"What if we changed the loop to increment count by 2 each time? How would the time complexity change?"