git add with patterns and directories - Time & Space Complexity

Time Complexity: git add with patterns and directories

O(n)

Understanding Time Complexity

When using git add with patterns or directories, Git must find all matching files to stage. Understanding how the time grows as the number of files increases helps us know how long this command might take.

We want to see how the work Git does changes when there are more files or complex patterns.

Scenario Under Consideration

Analyze the time complexity of the following git command:

git add src/**/*.js

This command stages all JavaScript files inside the src directory and its subdirectories matching the pattern.

Identify Repeating Operations

Git must look through files and folders to find matches.

• Primary operation: Traversing the directory tree and checking each file against the pattern.
• How many times: Once for each file and folder inside src and its subfolders.

How Execution Grows With Input

As the number of files grows, Git must check more files to see if they match the pattern.

Input Size (n files)	Approx. Operations
10	Checks about 10 files
100	Checks about 100 files
1000	Checks about 1000 files

Pattern observation: The work grows roughly in direct proportion to the number of files Git must check.

Final Time Complexity

Time Complexity: O(n)

This means the time Git takes grows linearly with the number of files it needs to examine.

Common Mistake

[X] Wrong: "Git instantly knows which files match the pattern without checking each one."

[OK] Correct: Git must look at each file to see if it fits the pattern, so more files mean more work.

Interview Connect

Knowing how commands like git add scale helps you understand real-world tool performance and prepares you to explain efficiency clearly and confidently.

Self-Check

"What if we changed the pattern to add only files in a single directory without recursion? How would the time complexity change?"