String comparisons (=, !=, -z, -n) in Bash Scripting - Time & Space Complexity

Time Complexity: String comparisons (=, !=, -z, -n)

O(n)

Understanding Time Complexity

When we compare strings in bash scripts, it is useful to know how the time taken grows as the strings get longer.

We want to understand how the cost of comparing strings changes with their size.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

str1="$1"
str2="$2"

if [ "$str1" = "$str2" ]; then
  echo "Strings are equal"
else
  echo "Strings are different"
fi

if [ -z "$str1" ]; then
  echo "First string is empty"
fi

This script compares two strings for equality and checks if the first string is empty.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing characters of two strings one by one.
• How many times: Up to the length of the shorter string, character by character.

How Execution Grows With Input

As the strings get longer, the comparison checks more characters until it finds a difference or reaches the end.

Input Size (n)	Approx. Operations
10	Up to 10 character comparisons
100	Up to 100 character comparisons
1000	Up to 1000 character comparisons

Pattern observation: The number of operations grows roughly in direct proportion to the string length.

Final Time Complexity

Time Complexity: O(n)

This means the time to compare strings grows linearly with the length of the strings.

Common Mistake

[X] Wrong: "String comparisons always take the same time no matter how long the strings are."

[OK] Correct: The comparison checks characters one by one, so longer strings usually take more time.

Interview Connect

Understanding how string comparison time grows helps you write efficient scripts and answer questions about performance clearly.

Self-Check

What if we used pattern matching instead of direct string comparison? How would the time complexity change?