Iterating over arrays in Bash Scripting - Time & Space Complexity

Time Complexity: Iterating over arrays

O(n)

Understanding Time Complexity

When we run a script that goes through each item in a list, it takes some time. We want to understand how this time changes as the list gets bigger.

The question is: How does the work grow when we look at more items?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

# Define an array
arr=(apple banana cherry date elderberry)

# Loop through each element
for item in "${arr[@]}"; do
  echo "$item"
done
    

This script prints each fruit name from the array one by one.

Identify Repeating Operations

• Primary operation: The for loop that goes through each item in the array.
• How many times: Once for every element in the array.

How Execution Grows With Input

As the array gets bigger, the script prints more items, so it takes longer.

Input Size (n)	Approx. Operations
10	10 print actions
100	100 print actions
1000	1000 print actions

Pattern observation: The work grows directly with the number of items. Double the items, double the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line with the number of items in the array.

Common Mistake

[X] Wrong: "The loop runs in constant time no matter how many items there are."

[OK] Correct: Each item needs to be handled once, so more items mean more work and more time.

Interview Connect

Understanding how loops grow with input size is a key skill. It helps you explain your code clearly and shows you know how to think about efficiency.

Self-Check

"What if we nested another loop inside to compare each item with every other item? How would the time complexity change?"

Practice

1. What is the correct way to iterate over all elements in a Bash array named fruits?

easy

A. for fruit in ${fruits[*]}; do echo "$fruit"; done

B. for fruit in ${fruits}; do echo "$fruit"; done

C. for fruit in "${fruits[@]}"; do echo "$fruit"; done

D. for fruit in fruits; do echo "$fruit"; done

Solution

1. Step 1: Understand array iteration syntax

   In Bash, to iterate over all elements of an array safely, you use "${array[@]}" which expands each element as a separate word, preserving spaces.

2. Step 2: Check each option's correctness

   for fruit in "${fruits[@]}"; do echo "$fruit"; done uses "${fruits[@]}" correctly. Options B and C omit quotes or use ${fruits} or ${fruits[*]} without quotes, which can break elements with spaces. for fruit in fruits; do echo "$fruit"; done treats fruits as a string, not an array.

3. Final Answer:

   for fruit in "${fruits[@]}"; do echo "$fruit"; done -> Option C

4. Quick Check:

   Use "${array[@]}" to iterate safely [OK]

Hint: Always quote "${array[@]}" to handle spaces safely [OK]

Common Mistakes:

• Not quoting "${array[@]}" causing word splitting
• Using ${array} instead of ${array[@]}
• Iterating over the array name as a string

2. Which of the following is the correct syntax to iterate over an array colors in Bash?

easy

A. for color in colors; do echo $color; done

B. for color in ${colors}; do echo $color; done

C. for color in ${colors[@]}; do echo $color; done

D. for color in "${colors[@]}"; do echo $color; done

Solution

1. Step 1: Identify correct quoting for array iteration

   To iterate over array elements safely, you must quote "${array[@]}" to preserve elements with spaces.

2. Step 2: Evaluate each option

   for color in "${colors[@]}"; do echo $color; done correctly uses quotes around "${colors[@]}". for color in colors; do echo $color; done treats 'colors' as a string, not an array. for color in ${colors[@]}; do echo $color; done misses quotes, risking word splitting. for color in ${colors}; do echo $color; done uses ${colors} which is incorrect for arrays.

3. Final Answer:

   for color in "${colors[@]}"; do echo $color; done -> Option D

4. Quick Check:

   Quote "${array[@]}" for safe iteration [OK]

Hint: Quote "${array[@]}" to avoid splitting elements [OK]

Common Mistakes:

• Forgetting quotes around "${array[@]}"
• Using array name without $ or quotes
• Using ${array} instead of ${array[@]}

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

names=("Alice" "Bob Smith" "Charlie")
for name in "${names[@]}"; do
  echo "$name"
done

medium

A. Alice
Bob Smith
Charlie

B. Alice
Bob
Smith
Charlie

C. Alice Bob Smith Charlie

D. Syntax error

Solution

1. Step 1: Understand array elements and quoting

   The array has three elements: "Alice", "Bob Smith", and "Charlie". Quoting "${names[@]}" preserves each element as one word, even if it contains spaces.

2. Step 2: Trace the loop output

   The loop prints each element on its own line: first "Alice", then "Bob Smith", then "Charlie".

3. Final Answer:

   Alice Bob Smith Charlie -> Option A

4. Quick Check:

   Quoted "${array[@]}" keeps elements intact [OK]

Hint: Quoted "${array[@]}" keeps multi-word elements together [OK]

Common Mistakes:

• Assuming elements split on spaces inside quotes
• Using unquoted ${array[@]} causing word splitting
• Expecting all elements on one line

4. Identify the error in this Bash script that tries to print all elements of array items:

items=("pen" "notebook" "eraser")
for i in ${items[@]}
do
  echo $i
done

medium

A. Array declaration syntax is wrong

B. Missing quotes around ${items[@]} causes word splitting

C. for loop syntax is incorrect

D. echo command is missing quotes

Solution

1. Step 1: Check array declaration

   The array declaration is correct with parentheses and quoted elements.

2. Step 2: Analyze the for loop iteration

   The loop uses unquoted ${items[@]}, which causes word splitting. If any element had spaces, it would split incorrectly. Quoting "${items[@]}" fixes this.

3. Final Answer:

   Missing quotes around ${items[@]} causes word splitting -> Option B

4. Quick Check:

   Always quote "${array[@]}" to avoid splitting [OK]

Hint: Quote "${array[@]}" to prevent splitting elements [OK]

Common Mistakes:

• Not quoting array expansion in loops
• Assuming echo needs quotes for correctness here
• Misreading array declaration syntax

5. You have a Bash array files containing filenames, some with spaces. You want to print only those filenames that contain the word "report". Which script correctly iterates and filters the array?

hard

A. for file in "${files[@]}"; do if [[ $file == *report* ]]; then echo "$file"; fi; done

B. for file in ${files[@]}; do if [[ $file == *report* ]]; then echo "$file"; fi; done

C. for file in "${files[*]}"; do if [[ $file == *report* ]]; then echo "$file"; fi; done

D. for file in files; do if [[ $file == *report* ]]; then echo "$file"; fi; done

Solution

1. Step 1: Choose correct array iteration with quoting

   To handle filenames with spaces correctly, iterate using "${files[@]}" quoted. This preserves each filename as one item.

2. Step 2: Apply filtering condition inside loop

   The condition [[ $file == *report* ]] correctly checks if the filename contains "report". for file in "${files[@]}"; do if [[ $file == *report* ]]; then echo "$file"; fi; done uses this with proper quoting and iteration.

3. Final Answer:

   for file in "${files[@]}"; do if [[ $file == *report* ]]; then echo "$file"; fi; done -> Option A

4. Quick Check:

   Quote "${array[@]}" and filter inside loop [OK]

Hint: Quote "${array[@]}" and filter inside loop with [[ ]] [OK]

Common Mistakes:

• Using unquoted ${files[@]} splitting filenames
• Using ${files[*]} which joins all elements into one string
• Iterating over literal 'files' string