C-style for loop in Bash Scripting - Time & Space Complexity

Time Complexity: C-style for loop

O(N)

Understanding Time Complexity

When we use a C-style for loop in bash, it is important to know how the time it takes to run changes as we increase the number of loop steps.

We want to find out how the total work grows when the loop runs more times.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for (( i=0; i<N; i++ )); do
  echo "Step $i"
done

This code runs a loop from 0 up to N-1, printing a message each time.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The loop runs the echo command once per iteration.
• How many times: Exactly N times, where N is the input size.

How Execution Grows With Input

As N grows, the number of times the loop runs grows the same way.

Input Size (N)	Approx. Operations
10	10 echo commands
100	100 echo commands
1000	1000 echo commands

Pattern observation: The work grows directly in proportion to N. Double N, double the work.

Final Time Complexity

Time Complexity: O(N)

This means the time to finish grows linearly as the number of loop steps increases.

Common Mistake

[X] Wrong: "The loop runs in constant time because it just prints one line."

[OK] Correct: Even though each step is simple, the loop runs N times, so total time grows with N, not fixed.

Interview Connect

Understanding how loops affect time helps you explain your code clearly and shows you can think about efficiency, a skill valued in many scripting tasks.

Self-Check

"What if we added a nested C-style for loop inside this loop? How would the time complexity change?"