Three-way merge in Git - Time & Space Complexity

Time Complexity: Three-way merge

O(n)

Understanding Time Complexity

When Git combines changes from different branches, it uses a three-way merge. Understanding how the time it takes grows helps us know how Git handles bigger projects.

We want to see how the work Git does changes as the files get larger or have more changes.

Scenario Under Consideration

Analyze the time complexity of the following git merge process.

# Assume we have a base commit, and two branches with changes
# Git performs a three-way merge:
# 1. Find the common ancestor (base)
# 2. Compare base with branch A changes
# 3. Compare base with branch B changes
# 4. Combine changes and resolve conflicts

git merge branchB
    

This snippet shows the key steps Git takes to merge two branches using a three-way merge.

Identify Repeating Operations

Look at what Git repeats during the merge:

• Primary operation: Comparing file contents line by line between base and each branch.
• How many times: For each file changed, Git compares lines twice (once per branch).

How Execution Grows With Input

As files get bigger or more files change, Git must compare more lines.

Input Size (n)	Approx. Operations
10 lines	About 20 line comparisons (10 lines x 2 branches)
100 lines	About 200 line comparisons
1000 lines	About 2000 line comparisons

Pattern observation: The work grows roughly in direct proportion to the number of lines changed.

Final Time Complexity

Time Complexity: O(n)

This means the time Git takes to merge grows linearly with the size of the changes it compares.

Common Mistake

[X] Wrong: "Git merge time depends on the total size of the whole project, not just changed files."

[OK] Correct: Git only compares the changed parts of files, so the merge time depends mostly on the size of changes, not the entire project.

Interview Connect

Knowing how Git merges changes helps you understand how tools handle growing projects. This skill shows you can think about efficiency in real work.

Self-Check

"What if Git had to merge changes from three branches instead of two? How would the time complexity change?"

Practice

1. What is the main purpose of a three-way merge in Git?

easy

A. To combine changes from two branches using a common base

B. To delete a branch after merging

C. To create a new branch from the current branch

D. To reset the current branch to a previous commit

Solution

1. Step 1: Understand the concept of three-way merge

   A three-way merge uses the common ancestor of two branches to combine their changes safely.

2. Step 2: Identify the purpose in Git workflow

   This process helps merge changes from two branches without losing work, especially when both branches have edits.

3. Final Answer:

   To combine changes from two branches using a common base -> Option A

4. Quick Check:

   Three-way merge = combine changes safely [OK]

Hint: Three-way merge combines two branches with a common ancestor [OK]

Common Mistakes:

• Confusing merge with branch deletion
• Thinking merge creates new branches
• Mixing merge with reset commands

2. Which Git command automatically performs a three-way merge when integrating changes from a remote branch?

easy

A. git pull

B. git merge

C. git commit

D. git branch

Solution

1. Step 1: Recall commands that fetch and merge

   git pull fetches changes from a remote branch and merges them locally, often using a three-way merge.

2. Step 2: Differentiate from other commands

   git merge merges branches locally but does not fetch remote changes; git branch manages branches; git commit records changes.

3. Final Answer:

   git pull -> Option A

4. Quick Check:

   git pull = fetch + merge (three-way) [OK]

Hint: git pull fetches and merges remotely with three-way merge [OK]

Common Mistakes:

• Choosing git merge without fetching first
• Confusing git commit with merge
• Using git branch for merging

3. Given the following scenario:

Branch A has file.txt with content: "Hello World"
Branch B modifies file.txt to: "Hello Git"
Common base has file.txt: "Hi World"

What will be the content of file.txt after a successful three-way merge of Branch B into Branch A?

medium

A. "Hello"

B. "Hello Git"

C. "Hello World Git"

D. "Hello World"

Solution

1. Step 1: Identify changes from base to each branch

   Base has "Hi World". Branch A changed "Hi" to "Hello". Branch B changed "Hi" to "Hello" and "World" to "Git".

2. Step 2: Understand three-way merge result

   Since the change "Hi" -> "Hello" is common to both branches, and Branch B has an additional change "World" -> "Git", Git's three-way merge automatically combines them, resulting in "Hello Git".

3. Final Answer:

   "Hello Git" -> Option B

4. Quick Check:

   Three-way merge picks combined changes, here "Hello Git" [OK]

Hint: Merged content reflects changes from both branches via base [OK]

Common Mistakes:

• Assuming content concatenates both changes
• Ignoring base version in merge
• Confusing which branch's changes apply

4. You ran git merge feature but got a conflict in app.js. What should you do to resolve this three-way merge conflict?

medium

A. Run git reset --hard immediately to discard all changes

B. Delete app.js and run git merge --abort

C. Edit app.js to fix conflicts, then run git add app.js and git commit

D. Run git branch -d feature to delete the feature branch

Solution

1. Step 1: Understand merge conflict resolution

   When a conflict occurs, you must manually edit the conflicting file to resolve differences.

2. Step 2: Stage and commit resolved file

   After fixing conflicts in app.js, use git add to stage and then git commit to complete the merge.

3. Final Answer:

   Edit app.js, then git add and git commit -> Option C

4. Quick Check:

   Fix conflicts, stage, commit to resolve merge [OK]

Hint: Fix conflicts manually, then add and commit [OK]

Common Mistakes:

• Deleting files instead of resolving conflicts
• Aborting merge without fixing conflicts
• Deleting branches to fix conflicts

5. You have two branches, main and feature. Both modified the same function in utils.py differently. After running git merge feature into main, a three-way merge conflict occurs. Which approach best resolves this conflict while preserving both changes?

hard

A. Delete feature branch and continue with main unchanged

B. Force merge with git merge --strategy=ours to keep main version only

C. Reset main to the common ancestor commit and retry merge

D. Manually edit utils.py to combine both changes logically, then stage and commit

Solution

1. Step 1: Recognize conflict in same function

   Both branches changed the same function differently, causing a conflict during merge.

2. Step 2: Choose best resolution method

   Manually editing the file to combine both changes logically preserves work from both branches, which is the best practice.

3. Step 3: Stage and commit after resolving

   After editing, stage the file with git add and commit to complete the merge.

4. Final Answer:

   Manually edit utils.py to combine changes, then stage and commit -> Option D

5. Quick Check:

   Manual merge preserves both changes best [OK]

Hint: Edit conflicts to combine changes, then add and commit [OK]

Common Mistakes:

• Using --strategy=ours loses feature changes
• Deleting branches to avoid conflicts
• Resetting loses recent work