Key-based authentication in Linux CLI - Time & Space Complexity

Time Complexity: Key-based authentication

O(n)

Understanding Time Complexity

We want to understand how the time needed to connect using key-based authentication changes as we try to connect to more servers.

How does the process time grow when the number of servers increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for server in $server_list; do
  ssh -i ~/.ssh/id_rsa user@${server} "uptime"
done

This script connects to each server in a list using key-based authentication and runs a simple command.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The ssh connection command inside the loop.
• How many times: Once for each server in the list.

How Execution Grows With Input

Each additional server adds one more ssh connection and command execution.

Input Size (n)	Approx. Operations
10	10 ssh connections and commands
100	100 ssh connections and commands
1000	1000 ssh connections and commands

Pattern observation: The total time grows directly with the number of servers.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete all connections grows in a straight line as you add more servers.

Common Mistake

[X] Wrong: "Connecting to multiple servers at once will take the same time as connecting to one."

[OK] Correct: Each connection takes its own time, so more servers mean more total time.

Interview Connect

Understanding how connection time grows helps you plan scripts that manage many servers efficiently and shows you think about scaling real tasks.

Self-Check

"What if we run ssh connections in parallel instead of one after another? How would the time complexity change?"