Indexed array declaration in Bash Scripting - Time & Space Complexity

Time Complexity: Indexed array declaration

O(n)

Understanding Time Complexity

We want to understand how the time it takes to create an indexed array grows as the number of elements increases.

Specifically, how does declaring and assigning values to an array behave when the array size changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

# Declare an indexed array and assign values
my_array=()
for ((i=1; i<=n; i++)); do
  my_array+=($i)
done
    

This code creates an empty indexed array and then adds numbers from 1 to n one by one.

Identify Repeating Operations

• Primary operation: Adding one element to the array inside the loop.
• How many times: The loop runs n times, once for each element added.

How Execution Grows With Input

Each new element is added one after another, so the total work grows as we add more elements.

Input Size (n)	Approx. Operations
10	10 additions
100	100 additions
1000	1000 additions

Pattern observation: The number of operations grows directly with n; doubling n doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to declare and fill the array grows linearly with the number of elements.

Common Mistake

[X] Wrong: "Adding elements to an array is instant and does not depend on the number of elements."

[OK] Correct: Each addition takes time, so more elements mean more total time, even if each step is quick.

Interview Connect

Understanding how loops and array operations scale helps you write efficient scripts and explain your code clearly in interviews.

Self-Check

"What if we declared the array with all elements at once instead of adding them one by one? How would the time complexity change?"