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?"

Practice

1. What does an until loop do in Ruby?

easy

A. Repeats code while the condition is false

B. Repeats code while the condition is true

C. Runs code only once

D. Stops code immediately

Solution

1. Step 1: Understand the until loop condition

   An until loop runs as long as its condition is false.

2. Step 2: Compare with while loop

   Unlike while which runs when true, until runs when false.

3. Final Answer:

   Repeats code while the condition is false -> Option A

4. Quick Check:

   Until loop runs while condition is false [OK]

Hint: Until loops run while condition is false, opposite of while [OK]

Common Mistakes:

• Thinking until runs while condition is true
• Confusing until with while loop
• Assuming until runs only once

2. Which of the following is the correct syntax for an until loop in Ruby?

easy

A. until condition then
# code
end

B. until (condition) {
# code
}

C. until condition:
# code

D. until condition do
# code
end

Solution

1. Step 1: Recall Ruby loop syntax

   Ruby uses until condition do ... end or just until condition ... end.

2. Step 2: Check each option

   until condition do # code end matches Ruby syntax; others use wrong symbols or keywords.

3. Final Answer:

   until condition do\n # code\nend -> Option D

4. Quick Check:

   Ruby until loop uses do/end syntax [OK]

Hint: Use do/end blocks for until loops in Ruby [OK]

Common Mistakes:

• Using curly braces {} instead of do/end
• Using colon : like Python
• Adding 'then' keyword incorrectly

3. What will be the output of this Ruby code?

count = 1
until count > 3 do
  puts count
  count += 1
end

medium

A. 1 2 3 4

B. 1 2 3

C. 2 3 4

D. No output

Solution

1. Step 1: Analyze the loop condition and variable

   The loop runs until count > 3. Starting from 1, it prints and increments count.

2. Step 2: Trace each iteration

   Prints 1, increments to 2; prints 2, increments to 3; prints 3, increments to 4; now count > 3, loop stops.

3. Final Answer:

   1 2 3 -> Option B

4. Quick Check:

   Prints 1 to 3 before stopping [OK]

Hint: Until runs while condition false, stops when count > 3 [OK]

Common Mistakes:

• Including 4 in output by mistake
• Thinking loop runs while condition true
• Forgetting to increment count

4. Identify the error in this Ruby code using an until loop:

i = 0
until i < 5
  puts i
  i += 1
end

medium

A. Infinite loop because i never changes

B. Missing do keyword after until condition

C. The loop condition should be > instead of <

D. No error, code runs correctly

Solution

1. Step 1: Analyze the loop condition

   until i < 5 with i=0: 0 < 5 is true, so condition true and loop never executes.

2. Step 2: Identify the correct error

   Syntax is fine (newline ok without do). Logic error: condition backwards. Should be until i > 4 or similar. The loop condition should be > instead of < identifies this.

3. Final Answer:

   The loop condition should be > instead of < -> Option C

4. Quick Check:

   Wrong condition direction: loop never runs [OK]

Hint: Flip < to > for until when adapting while logic [OK]

Common Mistakes:

• Confusing condition direction (< vs >)
• Assuming no do needed for until
• Thinking i doesn't change causing infinite loop

5. You want to write an until loop that prints numbers from 10 down to 1. Which code correctly does this?

hard

A. num = 10
until num < 1 do
puts num
num -= 1
end

B. num = 10
until num == 1 do
puts num
num -= 1
end

C. num = 10
until num > 0 do
puts num
num -= 1
end

D. num = 10
until num < 0 do
puts num
num -= 1
end

Solution

1. Step 1: Understand the goal and loop condition

   We want to print from 10 down to 1, so loop should run while num is >= 1.

2. Step 2: Check each option's condition

   num = 10 until num < 1 do puts num num -= 1 end uses until num < 1, meaning loop runs while num >= 1, printing 10 to 1 correctly.

3. Final Answer:

   num = 10\nuntil num < 1 do\n puts num\n num -= 1\nend -> Option A

4. Quick Check:

   Until runs while condition false, so until num < 1 runs until num is 0 [OK]

Hint: Use until num < 1 to count down from 10 to 1 [OK]

Common Mistakes:

• Using until num < 0 (prints 0 too)
• Using until num > 0 (never runs)
• Stopping at num == 1 (doesn't print 1)