git rebase basic usage - Time & Space Complexity

Time Complexity: git rebase basic usage

O(n)

Understanding Time Complexity

When using git rebase, it's helpful to know how the time it takes grows as the number of commits increases.

We want to understand how the work done by rebase changes when there are more commits to process.

Scenario Under Consideration

Analyze the time complexity of the following git rebase command.

git checkout feature-branch
# Switch to the feature branch

git rebase main
# Replay feature commits on top of main branch

This code moves the feature branch commits to start after the latest commit on main.

Identify Repeating Operations

Look for repeated work done during the rebase process.

• Primary operation: Applying each commit from the feature branch one by one onto the main branch.
• How many times: Once for each commit in the feature branch that is not in main.

How Execution Grows With Input

As the number of commits to rebase increases, the work grows proportionally.

Input Size (n)	Approx. Operations
10 commits	About 10 apply steps
100 commits	About 100 apply steps
1000 commits	About 1000 apply steps

Pattern observation: The time grows linearly with the number of commits to rebase.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the rebase grows directly with the number of commits being replayed.

Common Mistake

[X] Wrong: "Rebasing is instant no matter how many commits there are."

[OK] Correct: Each commit must be applied one after another, so more commits mean more work and more time.

Interview Connect

Understanding how git commands scale helps you explain your workflow choices clearly and shows you know what happens behind the scenes.

Self-Check

"What if we changed to an interactive rebase that skips some commits? How would the time complexity change?"

Practice

1. What does the git rebase command primarily do?

easy

A. Deletes all commits from the current branch

B. Merges two branches together with a merge commit

C. Creates a new branch without any commits

D. Moves your commits to a new base commit to create a linear history

Solution

1. Step 1: Understand the purpose of git rebase

   Git rebase moves commits from one base to another to keep history linear and clean.

2. Step 2: Compare with other git commands

   Unlike merge, rebase rewrites commit history without creating merge commits.

3. Final Answer:

   Moves your commits to a new base commit to create a linear history -> Option D

4. Quick Check:

   Rebase = move commits to new base [OK]

Hint: Rebase moves commits to a new base, unlike merge [OK]

Common Mistakes:

• Confusing rebase with merge
• Thinking rebase deletes commits
• Believing rebase creates new branches

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

easy

A. git rebase --merge main

B. git rebase -m main

C. git rebase main

D. git rebase --onto main

Solution

1. Step 1: Recall basic git rebase syntax

   The command to rebase current branch onto another is git rebase <branch>.

2. Step 2: Identify correct option

   git rebase main matches the correct syntax: git rebase main.

3. Final Answer:

   git rebase main -> Option C

4. Quick Check:

   Rebase syntax = git rebase branch [OK]

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

Common Mistakes:

• Adding unnecessary flags like -m or --merge
• Using --onto without required arguments
• Confusing rebase syntax with merge

3. Given the following commands run in sequence:

git checkout feature
git rebase main

What happens to the commits on feature branch?

medium

A. They are replayed on top of the latest commit on main

B. They are deleted and replaced by main commits

C. They remain unchanged and main is merged

D. They are copied to a new branch named main

Solution

1. Step 1: Understand what 'git rebase main' does on feature branch

   It takes commits from feature and replays them on top of main's latest commit.

2. Step 2: Clarify what happens to commits

   Commits are not deleted but moved to appear after main's commits, creating a linear history.

3. Final Answer:

   They are replayed on top of the latest commit on main -> Option A

4. Quick Check:

   Rebase = replay commits on new base [OK]

Hint: Rebase replays commits on top of target branch [OK]

Common Mistakes:

• Thinking commits get deleted
• Confusing rebase with merge
• Assuming new branches are created

4. You ran git rebase main on your feature branch but got conflicts. What is the correct way to continue after resolving conflicts?

medium

A. Run git rebase --continue

B. Run git merge --continue

C. Run git commit --amend

D. Run git rebase --abort to finish

Solution

1. Step 1: Identify the correct command after resolving rebase conflicts

   After fixing conflicts during rebase, you must run git rebase --continue to proceed.

2. Step 2: Differentiate from other commands

   git merge --continue is for merges, git commit --amend edits commits, and git rebase --abort cancels rebase.

3. Final Answer:

   Run git rebase --continue -> Option A

4. Quick Check:

   Fix conflicts then git rebase --continue [OK]

Hint: After conflicts, use 'git rebase --continue' to proceed [OK]

Common Mistakes:

• Using merge commands during rebase
• Aborting rebase instead of continuing
• Trying to amend commits prematurely

5. You rebased your feature branch onto main and now want to update the remote branch. What must you do to push your changes?

hard

A. Use git push normally without flags

B. Use git push --force to overwrite remote history

C. Delete the remote branch and push again

D. Use git push --no-verify to skip hooks

Solution

1. Step 1: Understand effect of rebase on commit history

   Rebase rewrites commit history, so remote branch history differs from local.

2. Step 2: Identify correct push method after rebase

   You must force push with git push --force to update remote branch with rewritten history.

3. Final Answer:

   Use git push --force to overwrite remote history -> Option B

4. Quick Check:

   Rebase requires force push to update remote [OK]

Hint: After rebase, always force push to update remote branch [OK]

Common Mistakes:

• Trying normal push after rebase
• Deleting remote branch unnecessarily
• Using push flags unrelated to rebase