Parallel execution patterns in Bash Scripting - Time & Space Complexity

Time Complexity: Parallel execution patterns

O(1)

Understanding Time Complexity

When running tasks in parallel in bash scripts, it is important to understand how the total time changes as we add more tasks.

We want to know how the execution time grows when multiple commands run at the same time.

Scenario Under Consideration

Analyze the time complexity of the following bash script using parallel execution.

for file in *.txt; do
  cat "$file" &
done
wait
    

This script runs the cat command on each text file in the folder at the same time, then waits for all to finish.

Identify Repeating Operations

Look for repeated actions that take time.

• Primary operation: Running cat on each file.
• How many times: Once per file, all started in parallel.

How Execution Grows With Input

Since all commands run at the same time, total time depends mostly on the longest single command.

Input Size (n)	Approx. Operations
10	Time of longest cat among 10 files
100	Time of longest cat among 100 files
1000	Time of longest cat among 1000 files

Pattern observation: Total time grows with the longest single task, not the number of tasks.

Final Time Complexity

Time Complexity: O(1)

This means the total time stays about the same no matter how many tasks run, assuming enough resources to run all in parallel.

Common Mistake

[X] Wrong: "Running more tasks in parallel always takes more time overall."

[OK] Correct: When tasks run truly in parallel, total time depends on the longest task, not the count of tasks.

Interview Connect

Understanding how parallel execution affects time helps you write faster scripts and shows you can think about efficiency in real situations.

Self-Check

What if we limit the number of parallel tasks to 5 at a time? How would the time complexity change?

Practice

1. What does adding & at the end of a command in a bash script do?

easy

A. Runs the command in the background, allowing the script to continue immediately

B. Stops the script until the command finishes

C. Redirects the command output to a file

D. Runs the command with higher priority

Solution

1. Step 1: Understand the role of & in bash

   The & symbol placed at the end of a command tells bash to run that command in the background.

2. Step 2: Effect on script execution

   Running a command in the background means the script does not wait for it to finish and continues to the next command immediately.

3. Final Answer:

   Runs the command in the background, allowing the script to continue immediately -> Option A

4. Quick Check:

   Background execution = & at end [OK]

Hint: Remember & means run in background, no waiting [OK]

Common Mistakes:

• Thinking & pauses the script until command finishes
• Confusing & with output redirection
• Assuming & changes command priority

2. Which of the following is the correct syntax to run two commands in parallel in bash?

easy

A. command1 & command2 &

B. command1 && command2 &

C. command1 && command2

D. command1 & command2

Solution

1. Step 1: Identify how to run commands in parallel

   Appending & to a command runs it in the background. To run two commands in parallel, both must have &.

2. Step 2: Analyze options

   command1 & command2 & runs both commands with &, so both run in background simultaneously. command1 && command2 & uses && which means run second only if first succeeds, then runs second in background (but first runs in foreground). command1 && command2 uses && without background. command1 & command2 runs command1 in background but command2 in foreground, so the script blocks until command2 finishes.

3. Final Answer:

   command1 & command2 & -> Option A

4. Quick Check:

   Both commands need & to run parallel [OK]

Hint: Use & after each command to run both in parallel [OK]

Common Mistakes:

• Using && which runs commands sequentially
• Missing & on second command
• Confusing & with &&

3. What will be the output order of the following script?

echo "Start"
sleep 2 &
echo "Middle"
sleep 1 &
echo "End"
wait

medium

A. Start\nMiddle\nEnd\n(wait blocks output until sleeps finish)

B. Start\n(wait)\nMiddle\nEnd

C. Start\nMiddle\nEnd (then waits for sleeps to finish)

D. Start\nEnd\nMiddle

Solution

1. Step 1: Understand background jobs and output

   The sleep commands run in background due to &, so they do not block the script. The echo commands run immediately in order.

2. Step 2: Analyze output order

   The script prints "Start", then starts sleep 2 in background, then prints "Middle", starts sleep 1 in background, then prints "End". The wait pauses script exit until sleeps finish but does not affect output order.

3. Final Answer:

   Start\nMiddle\nEnd (then waits for sleeps to finish) -> Option C

4. Quick Check:

   Background jobs don't block echo output [OK]

Hint: Background jobs run silently; echo prints immediately [OK]

Common Mistakes:

• Assuming wait delays echo output
• Thinking sleep blocks echo
• Confusing order of background jobs

4. Identify the error in this script snippet that tries to run two commands in parallel and wait for both:

command1 &
command2
wait

medium

A. command1 & syntax is incorrect

B. wait command is missing arguments

C. Both commands run sequentially, no parallelism

D. command2 is not run in background, so wait only waits for command1

Solution

1. Step 1: Check background execution of commands

   Only command1 has & to run in background. command2 runs in foreground, blocking until it finishes.

2. Step 2: Effect on wait

   The wait command waits for all background jobs to finish. Since only command1 is background, wait waits only for it. command2 runs before wait.

3. Final Answer:

   command2 is not run in background, so wait only waits for command1 -> Option D

4. Quick Check:

   All parallel commands need & before wait [OK]

Hint: Add & to all parallel commands before wait [OK]

Common Mistakes:

• Forgetting & on second command
• Thinking wait needs arguments
• Assuming wait waits for foreground commands

5. You want to run 3 independent scripts script1.sh, script2.sh, and script3.sh in parallel and then print "All done" only after all finish. Which is the best way to do this?

hard

A. ./script1.sh && ./script2.sh && ./script3.sh && echo "All done"

B. ./script1.sh &
./script2.sh &
./script3.sh &
wait
echo "All done"

C. ./script1.sh & ./script2.sh & ./script3.sh & echo "All done"

D. ./script1.sh &
./script2.sh &
./script3.sh
echo "All done"

Solution

1. Step 1: Run all scripts in background

   Adding & after each script runs them in parallel without waiting.

2. Step 2: Use wait to pause until all finish

   The wait command pauses the script until all background jobs complete, ensuring synchronization.

3. Step 3: Print message after all finish

   After wait, echo "All done" runs, confirming all scripts finished.

4. Final Answer:

   ./script1.sh &
   ./script2.sh &
   ./script3.sh &
   wait
   echo "All done"

   -> Option B

5. Quick Check:

   Background + wait + echo after = correct pattern [OK]

Hint: Use & for parallel, then wait before next step [OK]

Common Mistakes:

• Using && runs scripts sequentially
• Missing wait causes echo to run too early
• Putting echo on same line with & causes immediate print