Fast-forward merge in Git - Time & Space Complexity

Time Complexity: Fast-forward merge

O(n)

Understanding Time Complexity

We want to understand how the time to complete a fast-forward merge changes as the number of commits grows.

How does git handle merging when no new commits diverge?

Scenario Under Consideration

Analyze the time complexity of this fast-forward merge command.

git checkout main
# main is behind feature branch

git merge feature

This code moves the main branch pointer forward to the feature branch if no divergent commits exist.

Identify Repeating Operations

Look for repeated steps git does during the merge.

• Primary operation: Checking commit ancestry to confirm fast-forward is possible.
• How many times: Git checks commits from main up to feature branch, proportional to the number of commits ahead.

How Execution Grows With Input

As the number of commits ahead on the feature branch grows, git must verify each commit to confirm fast-forward.

Input Size (n)	Approx. Operations
10 commits ahead	About 10 commit checks
100 commits ahead	About 100 commit checks
1000 commits ahead	About 1000 commit checks

Pattern observation: The work grows linearly with the number of commits to move forward.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete a fast-forward merge grows directly with how many commits are ahead.

Common Mistake

[X] Wrong: "Fast-forward merge happens instantly no matter how many commits are ahead."

[OK] Correct: Git must check each commit to confirm the fast-forward is valid, so more commits mean more work.

Interview Connect

Understanding this helps you explain how git efficiently moves branches and why some merges take longer than others.

Self-Check

What if the merge was not fast-forward but required a real merge commit? How would the time complexity change?

Practice

1. What happens during a fast-forward merge in Git?

easy

A. The source branch is deleted automatically.

B. A new merge commit is always created.

C. The branch pointer moves forward without creating a new commit.

D. The commit history becomes non-linear.

Solution

1. Step 1: Understand fast-forward merge behavior

   A fast-forward merge moves the branch pointer forward to the latest commit of the source branch without creating a new merge commit.

2. Step 2: Compare with other merge types

   Unlike a normal merge, it does not create a new commit and keeps history linear.

3. Final Answer:

   The branch pointer moves forward without creating a new commit. -> Option C

4. Quick Check:

   Fast-forward merge = pointer moves forward [OK]

Hint: Fast-forward means no new commit, just pointer moves [OK]

Common Mistakes:

• Thinking a merge commit is always created
• Assuming source branch deletes automatically
• Believing history becomes non-linear

2. Which Git command syntax performs a fast-forward merge of branch feature into main only if possible, otherwise aborts?

easy

A. git merge --squash feature

B. git merge feature

C. git merge --no-ff feature

D. git merge --ff-only feature

Solution

1. Step 1: Identify command for fast-forward only

   The option --ff-only tells Git to merge only if it can fast-forward, otherwise it aborts.

2. Step 2: Compare other options

   --no-ff disables fast-forward, --squash creates a single commit without merging, and plain git merge feature may create a merge commit.

3. Final Answer:

   git merge --ff-only feature -> Option D

4. Quick Check:

   Fast-forward only = --ff-only [OK]

Hint: Use --ff-only to ensure only fast-forward merges happen [OK]

Common Mistakes:

• Using --no-ff disables fast-forward merges
• Assuming plain merge always fast-forwards
• Confusing --squash with fast-forward

3. Given the following Git commands, what is the output of git log --oneline main after merging?

git checkout main
# main points to commit A

git checkout -b feature
# feature branch created from A

git commit --allow-empty -m "Add feature commit"
# feature now points to commit B

git checkout main

git merge feature

medium

A. B

B. B\nA

C. A

D. Merge commit with A and B

Solution

1. Step 1: Understand branch states before merge

   Main points to commit A. Feature branch adds commit B on top of A.

2. Step 2: Analyze merge behavior

   Since main has no new commits after branching, merging feature into main will fast-forward main to B.

3. Final Answer:

   B\nA -> Option B

4. Quick Check:

   Fast-forward merge moves main to B [OK]

Hint: If main unchanged, merge moves pointer to feature commit [OK]

Common Mistakes:

• Expecting merge commit creation
• Thinking main stays at A
• Confusing commit hashes output

4. You tried to fast-forward merge branch feature into main using git merge --ff-only feature, but Git returned an error. What is the most likely cause?

medium

A. The main branch has new commits not in feature.

B. The feature branch is behind main.

C. The feature branch has no commits.

D. You forgot to commit changes on feature branch.

Solution

1. Step 1: Understand --ff-only error cause

   The --ff-only option fails if a fast-forward merge is not possible.

2. Step 2: Identify when fast-forward is impossible

   If main has new commits not in feature, Git cannot fast-forward main to feature, causing the error.

3. Final Answer:

   The main branch has new commits not in feature. -> Option A

4. Quick Check:

   Fast-forward fails if main has new commits [OK]

Hint: Fast-forward fails if main moved ahead since branching [OK]

Common Mistakes:

• Assuming feature must be behind main
• Thinking empty feature branch causes error
• Confusing uncommitted changes with merge errors

5. You have a main branch and a feature branch. Both have new commits since branching. You want to merge feature into main but keep history linear without merge commits. Which approach is best?

hard

A. Use git rebase main on feature, then fast-forward merge.

B. Use git merge --no-ff feature to force a merge commit.

C. Use git merge --ff-only feature and abort if not fast-forward.

D. Delete main and rename feature to main.

Solution

1. Step 1: Understand the problem with fast-forward

   Since both branches have new commits, a fast-forward merge is not possible directly.

2. Step 2: Use rebase to linearize history

   Rebasing feature onto main moves feature commits on top of main, enabling a fast-forward merge afterward.

3. Step 3: Perform fast-forward merge after rebase

   After rebase, merging feature into main will be a fast-forward, keeping history linear without merge commits.

4. Final Answer:

   Use git rebase main on feature, then fast-forward merge. -> Option A

5. Quick Check:

   Rebase then merge = linear history [OK]

Hint: Rebase feature on main to enable fast-forward merge [OK]

Common Mistakes:

• Trying --ff-only merge when not possible
• Forcing merge commit breaks linear history
• Deleting branches unnecessarily