Rebase vs merge mental model in Git - Performance Comparison

Time Complexity: Rebase vs merge mental model

O(n)

Understanding Time Complexity

When using Git, combining changes from different branches can be done by merging or rebasing. Understanding how the time to combine grows with the number of commits helps us choose the right method.

We want to know: How does the work Git does increase as the number of commits to combine grows?

Scenario Under Consideration

Analyze the time complexity of these Git commands:

git merge main

git rebase main

These commands combine changes from one branch into another, but in different ways.

Identify Repeating Operations

Look at what Git does internally when running these commands:

• Primary operation: For merge, Git compares the latest commits and creates a new commit combining changes. For rebase, Git re-applies each commit from the feature branch one by one onto the main branch.
• How many times: Merge does a single combine operation regardless of commits. Rebase repeats the apply step once per commit in the feature branch.

How Execution Grows With Input

Imagine the feature branch has different numbers of commits to combine:

Input Size (n commits)	Approx. Operations
10	Merge: 1 combine, Rebase: 10 applies
100	Merge: 1 combine, Rebase: 100 applies
1000	Merge: 1 combine, Rebase: 1000 applies

Pattern observation: Merge work stays the same no matter how many commits. Rebase work grows linearly with the number of commits.

Final Time Complexity

Time Complexity: O(n)

This means the time Git takes to rebase grows directly with the number of commits, while merge time stays mostly constant.

Common Mistake

[X] Wrong: "Rebase and merge take the same time no matter how many commits there are."

[OK] Correct: Merge combines all changes at once, but rebase applies each commit separately, so more commits mean more work for rebase.

Interview Connect

Knowing how Git commands scale with commit count shows you understand their inner workings. This helps you explain your choices clearly and confidently in real projects or interviews.

Self-Check

"What if we used interactive rebase to squash commits before rebasing? How would that affect the time complexity?"

Practice

1. What is the main difference between git merge and git rebase?

easy

A. git merge rewrites commit messages; git rebase preserves commit messages.

B. git merge deletes the source branch; git rebase deletes the target branch.

C. git merge only works on remote branches; git rebase only works on local branches.

D. git merge combines histories preserving all commits; git rebase rewrites history to create a linear sequence.

Solution

1. Step 1: Understand git merge behavior

   git merge combines two branches by creating a new commit that preserves the history of both branches without changing existing commits.

2. Step 2: Understand git rebase behavior

   git rebase moves or reapplies commits from one branch onto another, rewriting history to make it look like a straight line.

3. Final Answer:

   git merge combines histories preserving all commits; git rebase rewrites history to create a linear sequence. -> Option D

4. Quick Check:

   Merge preserves history, rebase rewrites it [OK]

Hint: Merge keeps history; rebase rewrites it linearly [OK]

Common Mistakes:

• Thinking merge deletes branches
• Believing rebase only works on remote branches
• Confusing which command rewrites history

2. Which of the following is the correct syntax to rebase the current branch onto main?

easy

A. git rebase main

B. git merge main

C. git rebase origin/main

D. git checkout main && git rebase

Solution

1. Step 1: Identify the command to rebase current branch

   The command git rebase main rebases the current branch onto the main branch.

2. Step 2: Check other options for correctness

   git merge main merges, not rebases; git rebase origin/main rebases onto remote tracking branch which may be outdated; git checkout main && git rebase is invalid syntax.

3. Final Answer:

   git rebase main -> Option A

4. Quick Check:

   Rebase current branch onto main = git rebase main [OK]

Hint: Use 'git rebase branch-name' to rebase current branch [OK]

Common Mistakes:

• Using merge instead of rebase
• Rebasing onto remote branch without fetching
• Incorrect chaining of commands

3. Given the following commands executed in order on branch feature:

git checkout feature
git rebase main
git log --oneline --graph

What will the commit history look like compared to using git merge main instead?

medium

A. A linear history with feature commits on top of main commits.

B. A merge commit combining main and feature histories.

C. No change in history; feature branch remains separate.

D. Feature branch commits are deleted.

Solution

1. Step 1: Understand effect of git rebase main on feature branch

   Rebasing moves feature commits to be based on the latest main commits, creating a straight, linear history.

2. Step 2: Compare with git merge main effect

   Merging creates a new merge commit that combines histories, preserving the branch structure and showing a branch point.

3. Final Answer:

   A linear history with feature commits on top of main commits. -> Option A

4. Quick Check:

   Rebase = linear history; merge = merge commit [OK]

Hint: Rebase = linear history; merge = merge commit [OK]

Common Mistakes:

• Thinking rebase creates merge commits
• Believing history stays unchanged after rebase
• Assuming commits are deleted after rebase

4. You ran git rebase main on your feature branch but got conflicts. After resolving conflicts, which command should you run to continue the rebase?

medium

A. git commit -m 'resolved conflicts'

B. git merge --continue

C. git rebase --continue

D. git rebase --abort

Solution

1. Step 1: Identify the correct command to continue rebase after conflicts

   After resolving conflicts during a rebase, git rebase --continue tells Git to proceed with applying remaining commits.

2. Step 2: Understand other options

   git merge --continue is for merge conflicts, not rebase; git commit -m is manual commit but rebase expects --continue; git rebase --abort cancels the rebase.

3. Final Answer:

   git rebase --continue -> Option C

4. Quick Check:

   Continue rebase after conflicts = git rebase --continue [OK]

Hint: Use 'git rebase --continue' after resolving conflicts [OK]

Common Mistakes:

• Using merge commands during rebase
• Trying to commit manually instead of continuing
• Aborting instead of continuing rebase

5. You want to update your feature branch with the latest changes from main but keep a clean, linear history without merge commits. Which sequence of commands achieves this safely?

hard

A. git checkout feature; git merge origin/main

B. git checkout feature; git fetch origin; git rebase origin/main

C. git checkout main; git pull; git checkout feature; git merge main

D. git checkout feature; git pull origin main

Solution

1. Step 1: Fetch latest changes from remote main branch

   git fetch origin updates local remote tracking branches without changing working branches.

2. Step 2: Rebase feature branch onto updated origin/main

   git rebase origin/main reapplies feature commits on top of latest main commits, keeping history linear and clean.

3. Final Answer:

   git checkout feature; git fetch origin; git rebase origin/main -> Option B

4. Quick Check:

   Fetch then rebase for clean update [OK]

Hint: Fetch first, then rebase onto remote main for clean history [OK]

Common Mistakes:

• Merging instead of rebasing for linear history
• Pulling directly on feature branch causing merge commits
• Not fetching latest remote changes before rebase