Calling functions in Bash Scripting - Time & Space Complexity

Time Complexity: Calling functions

O(n)

Understanding Time Complexity

When we call functions in a bash script, it is important to know how the time to run the script changes as we call these functions more or with bigger inputs.

We want to understand how the number of function calls affects the total work done.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function greet() {
  echo "Hello, $1!"
}

for name in Alice Bob Charlie Dave Eve; do
  greet "$name"
done

This script defines a function that prints a greeting, then calls it once for each name in a list of five names.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Calling the greet function inside a loop.
• How many times: Once for each name in the list (5 times here, but depends on list size).

How Execution Grows With Input

Each time we add one more name, the function is called one more time, so the total work grows directly with the number of names.

Input Size (n)	Approx. Operations
10	10 function calls
100	100 function calls
1000	1000 function calls

Pattern observation: The total work grows in a straight line as the input size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the script grows directly in proportion to the number of function calls.

Common Mistake

[X] Wrong: "Calling a function once or multiple times does not affect the total time much."

[OK] Correct: Each function call takes time, so calling it many times adds up and increases total running time.

Interview Connect

Understanding how function calls add up helps you write scripts that run efficiently and shows you can think about how your code behaves as it grows.

Self-Check

"What if the function itself contained a loop that runs n times? How would the time complexity change?"