Adding and removing elements in Bash Scripting - Time & Space Complexity

Time Complexity: Adding and removing elements

O(n^2)

Understanding Time Complexity

When we add or remove elements in a bash script, it is important to know how the time it takes grows as we handle more items.

We want to find out how the number of operations changes when the list of elements gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

# Initialize an empty array
items=()

# Add elements to the array
for i in $(seq 1 $n); do
  items+=("item$i")
done

# Remove elements from the array
for i in $(seq 1 $n); do
  items=("${items[@]:1}")
done

This script adds n elements to an array one by one, then removes n elements from the start one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding elements to the array and removing the first element repeatedly.
• How many times: Each loop runs n times, where n is the number of elements.

How Execution Grows With Input

Adding elements grows linearly because each addition is simple. Removing the first element each time is more costly because the array shifts elements.

Input Size (n)	Approx. Operations
10	About 10 additions + 45 shifts when removing
100	About 100 additions + 4950 shifts when removing
1000	About 1000 additions + 499500 shifts when removing

Pattern observation: Adding grows straight with n, but removing the first element repeatedly causes the work to grow much faster, roughly like n squared.

Final Time Complexity

Time Complexity: O(n2)

This means the total time grows roughly with the square of the number of elements because removing the first element shifts all others each time.

Common Mistake

[X] Wrong: "Removing the first element from an array is always a quick, constant-time operation."

[OK] Correct: In bash, removing the first element causes all later elements to move forward, so the time grows with the number of elements left.

Interview Connect

Understanding how adding and removing elements affects time helps you write efficient scripts and explain your choices clearly in real situations.

Self-Check

What if we removed elements from the end of the array instead of the start? How would the time complexity change?