until loop in Bash Scripting - 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 the loop runs affects the total work done.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

count=1
until [ $count -gt 5 ]
do
  echo "Count is $count"
  ((count++))
done

This code prints numbers from 1 to 5 using an until loop that stops when count is greater than 5.

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 value of count until the condition is met.

How Execution Grows With Input

As the stopping number grows, the loop runs more times, increasing work linearly.

Input Size (n)	Approx. Operations
5	5 loop runs
10	10 loop runs
100	100 loop runs

Pattern observation: The number of loop runs grows directly with the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line as the input number grows.

Common Mistake

[X] Wrong: "The until loop always runs a fixed number of times no matter the input."

[OK] Correct: The loop runs until a condition is true, so if the stopping number changes, the loop runs more or fewer times.

Interview Connect

Understanding how loops grow with input helps you explain script efficiency clearly and confidently in real situations.

Self-Check

"What if we changed the loop to count down from n to 1? How would the time complexity change?"