Why diffing matters in Git - Performance Analysis

Time Complexity: Why diffing matters

O(n*m)

Understanding Time Complexity

When using git, comparing changes between files is common. This comparison is called diffing.

We want to understand how the time to find differences grows as files get bigger.

Scenario Under Consideration

Analyze the time complexity of the following git diff command.

# Compare changes between two files
$ git diff file1.txt file2.txt
    

This command shows line-by-line differences between two versions of a file.

Identify Repeating Operations

Git diff compares lines from both files to find changes.

• Primary operation: Comparing lines between two files.
• How many times: Each line in one file is compared to lines in the other file.

How Execution Grows With Input

As the number of lines in files grows, the comparisons increase quickly.

Input Size (n lines)	Approx. Operations
10	About 100 comparisons
100	About 10,000 comparisons
1000	About 1,000,000 comparisons

Pattern observation: The number of comparisons grows roughly with the product of the number of lines in both files.

Final Time Complexity

Time Complexity: O(n*m)

This means the time to find differences grows with the product of the number of lines in both files.

Common Mistake

[X] Wrong: "Diffing time grows only with the size of one file."

[OK] Correct: Diffing compares both files line by line, so both sizes affect the time.

Interview Connect

Understanding how diffing scales helps you explain efficiency in version control tasks clearly and confidently.

Self-Check

What if git diff compared files word-by-word instead of line-by-word? How would the time complexity change?

Practice

1. What is the main purpose of using git diff in a project?

easy

A. To delete files from the repository

B. To create a new branch

C. To merge two branches automatically

D. To see the exact changes made between file versions

Solution

1. Step 1: Understand the function of git diff

   git diff shows differences between file versions or commits.

2. Step 2: Identify what git diff does not do

   It does not delete files, merge branches, or create branches.

3. Final Answer:

   To see the exact changes made between file versions -> Option D

4. Quick Check:

   Diffing = showing changes [OK]

Hint: Diff means showing changes between versions [OK]

Common Mistakes:

• Confusing diff with branch creation
• Thinking diff deletes files
• Assuming diff merges branches

2. Which of the following is the correct command to see unstaged changes in your working directory?

easy

A. git diff

B. git diff --staged

C. git status -s

D. git log

Solution

1. Step 1: Recall the meaning of git diff

   git diff shows unstaged changes in your working directory compared to the last commit.

2. Step 2: Understand other commands

   git diff --staged shows staged changes, git status -s shows status summary, and git log shows commit history.

3. Final Answer:

   git diff -> Option A

4. Quick Check:

   Unstaged changes = git diff [OK]

Hint: Use plain git diff for unstaged changes [OK]

Common Mistakes:

• Using git diff --staged for unstaged changes
• Confusing git status with diff output
• Using git log to see file changes

3. Given the following commands run in a git repository:

echo 'Hello' > file.txt
git add file.txt
echo 'World' >> file.txt
git diff

What will git diff show?

medium

A. The difference showing the addition of 'World' in file.txt

B. The entire content of file.txt

C. No output because all changes are staged

D. An error because file.txt is staged

Solution

1. Step 1: Analyze the commands

   First, 'Hello' is written and staged with git add. Then 'World' is appended but not staged.

2. Step 2: Understand what git diff shows

   git diff shows unstaged changes compared to the index (staged files). So it will show the addition of 'World'.

3. Final Answer:

   The difference showing the addition of 'World' in file.txt -> Option A

4. Quick Check:

   git diff = unstaged changes [OK]

Hint: git diff shows changes after last staging [OK]

Common Mistakes:

• Thinking git diff shows staged changes
• Expecting full file content output
• Assuming git diff errors on staged files

4. You ran git diff but it shows no output even though you edited a file. What is the most likely reason?

medium

A. You forgot to save the file after editing

B. You staged the changes with git add

C. You are on the wrong branch

D. The file is ignored by .gitignore

Solution

1. Step 1: Understand what git diff shows

   git diff shows unstaged changes in saved files.

2. Step 2: Consider why no changes appear

   If the changes are staged with git add, git diff shows no output because there are no unstaged changes.

3. Final Answer:

   You staged the changes with git add -> Option B

4. Quick Check:

   Staged changes = no unstaged diff output [OK]

Hint: Stage changes to clear unstaged diff output [OK]

Common Mistakes:

• Assuming staged changes show in git diff
• Thinking branch affects unstaged diff
• Confusing ignored files with unstaged changes

5. You want to review changes between two commits abc123 and def456. Which command correctly shows the differences?

hard

A. git diff --compare abc123..def456

B. git diff --staged abc123 def456

C. git diff abc123..def456

D. git diff --between abc123 def456

Solution

1. Step 1: Recall correct syntax for comparing commits

   The correct syntax uses two commit hashes separated by two dots: git diff abc123..def456.

2. Step 2: Identify invalid options

   git diff --staged abc123 def456 is invalid syntax, and options with --between or --compare do not exist.

3. Final Answer:

   git diff abc123..def456 -> Option C

4. Quick Check:

   Commit range uses two dots [OK]

Hint: Use two dots between commits for diff [OK]

Common Mistakes:

• Using git diff --staged for commit diffs
• Adding unsupported flags like --between
• Confusing diff syntax with log syntax