Interactive rebase (git rebase -i) - Time & Space Complexity

Time Complexity: Interactive rebase (git rebase -i)

O(n)

Understanding Time Complexity

When using interactive rebase in Git, it is important to understand how the time it takes grows as you work with more commits.

We want to know how the number of commits affects the work Git does during rebase.

Scenario Under Consideration

Analyze the time complexity of the following git interactive rebase command.

git rebase -i HEAD~5

# This opens an editor to reorder, squash, or edit the last 5 commits.
# Git will then replay these commits one by one on top of the base commit.
    

This command lets you change the last 5 commits by replaying them interactively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Git replays each commit one by one during the rebase.
• How many times: Once for each commit in the range (here, 5 times).

How Execution Grows With Input

As the number of commits to rebase increases, Git must replay more commits, so the work grows linearly.

Input Size (n)	Approx. Operations
10	Replays 10 commits
100	Replays 100 commits
1000	Replays 1000 commits

Pattern observation: Doubling the commits roughly doubles the work Git does during rebase.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the interactive rebase grows directly with the number of commits you want to change.

Common Mistake

[X] Wrong: "Interactive rebase time stays the same no matter how many commits I edit."

[OK] Correct: Each commit must be replayed, so more commits mean more work and longer time.

Interview Connect

Understanding how operations scale with input size shows you think about efficiency, a key skill in real-world software work.

Self-Check

"What if we only rebase a single commit instead of many? How would the time complexity change?"

Practice

1. What is the main purpose of using git rebase -i (interactive rebase)?

easy

A. To reorder, edit, or combine recent commits before sharing

B. To create a new branch from the current commit

C. To permanently delete the entire commit history

D. To push commits directly to the remote repository

Solution

1. Step 1: Understand the purpose of interactive rebase

   Interactive rebase allows you to change the order, combine, edit, or remove recent commits.

2. Step 2: Compare with other git commands

   Creating branches, deleting history, or pushing commits are different git operations.

3. Final Answer:

   To reorder, edit, or combine recent commits before sharing -> Option A

4. Quick Check:

   Interactive rebase = reorder/edit commits [OK]

Hint: Interactive rebase = rewrite recent commits easily [OK]

Common Mistakes:

• Confusing rebase with branch creation
• Thinking it deletes all history
• Assuming it pushes commits automatically

2. Which of the following is the correct command to start an interactive rebase for the last 3 commits?

easy

A. git rebase -i HEAD^^3

B. git rebase -i HEAD~3

C. git rebase -i HEAD~

D. git rebase -i HEAD^3

Solution

1. Step 1: Recall the syntax for interactive rebase

   The correct syntax uses HEAD~N to specify the last N commits, so HEAD~3 means last 3 commits.

2. Step 2: Check the options

   HEAD^3 and HEAD^^3 are invalid for this purpose; HEAD~ alone is incomplete.

3. Final Answer:

   git rebase -i HEAD~3 -> Option B

4. Quick Check:

   HEAD~3 selects last 3 commits [OK]

Hint: Use HEAD~N to select last N commits for rebase [OK]

Common Mistakes:

• Using HEAD^3 instead of HEAD~3
• Omitting the number after ~
• Using double carets ^^ incorrectly

3. Given the following interactive rebase todo list:

pick a1b2c3 Commit A
pick d4e5f6 Commit B
pick 789abc Commit C

If you change it to:

pick d4e5f6 Commit B
squash 789abc Commit C
pick a1b2c3 Commit A

What will happen after completing the rebase?

medium

A. Only Commit C will be applied, others dropped

B. Commits A and B will be combined, Commit C will be last

C. The rebase will fail due to invalid order

D. Commits B and C will be combined, and Commit A will be last

Solution

1. Step 1: Understand 'pick' and 'squash' in rebase

   'pick' applies a commit as is; 'squash' combines the commit with the previous one.

2. Step 2: Analyze the new order

   Commit B is picked first, Commit C is squashed into B, Commit A is picked last.

3. Final Answer:

   Commits B and C will be combined, and Commit A will be last -> Option D

4. Quick Check:

   squash merges commits; order changed [OK]

Hint: Squash merges commit into previous one in order [OK]

Common Mistakes:

• Thinking squash drops commits
• Assuming order stays same after rebase
• Confusing squash with fixup

4. You run git rebase -i HEAD~2 and change the second commit's action from pick to edit. After saving, what should you do next to modify that commit?

medium

A. Make changes, then run git commit --amend and git rebase --continue

B. Run git push immediately to update remote

C. Abort the rebase with git rebase --abort

D. Run git reset --hard HEAD~1 to undo the commit

Solution

1. Step 1: Understand 'edit' in interactive rebase

   When a commit is marked 'edit', rebase pauses to let you change it.

2. Step 2: Modify commit and continue rebase

   You make changes, amend the commit with git commit --amend, then continue with git rebase --continue.

3. Final Answer:

   Make changes, then run git commit --amend and git rebase --continue -> Option A

4. Quick Check:

   Edit = amend commit + continue rebase [OK]

Hint: Edit commit: amend changes, then continue rebase [OK]

Common Mistakes:

• Pushing before finishing rebase
• Aborting instead of continuing
• Resetting commits incorrectly

5. You want to clean up your last 4 commits by combining the second and third commits into one, and also reorder commits so the last commit becomes the first. Which interactive rebase todo list correctly achieves this?

pick 111aaa Commit 1
pick 222bbb Commit 2
pick 333ccc Commit 3
pick 444ddd Commit 4

hard

A. pick 444ddd Commit 4
squash 222bbb Commit 2
pick 333ccc Commit 3
pick 111aaa Commit 1

B. pick 444ddd Commit 4
pick 111aaa Commit 1
squash 222bbb Commit 2
pick 333ccc Commit 3

C. pick 444ddd Commit 4
pick 111aaa Commit 1
pick 222bbb Commit 2
squash 333ccc Commit 3

D. pick 111aaa Commit 1
pick 333ccc Commit 3
squash 222bbb Commit 2
pick 444ddd Commit 4

Solution

1. Step 1: Reorder commits to put last commit first

   Commit 4 (444ddd) should be first in the list to reorder it first.

2. Step 2: Combine second and third commits

   To combine commits 2 and 3, use 'pick' on commit 2 and 'squash' on commit 3 immediately after.

3. Step 3: Verify the todo list

   pick 444ddd Commit 4
   pick 111aaa Commit 1
   pick 222bbb Commit 2
   squash 333ccc Commit 3

   places commit 4 first, then commit 1, then picks commit 2 and squashes commit 3, matching requirements.

4. Final Answer:

   pick 444ddd Commit 4
   pick 111aaa Commit 1
   pick 222bbb Commit 2
   squash 333ccc Commit 3

   -> Option C

5. Quick Check:

   Reorder + squash =

   pick 444ddd Commit 4
   pick 111aaa Commit 1
   pick 222bbb Commit 2
   squash 333ccc Commit 3

   [OK]

Hint: Put last commit first, squash 3rd into 2nd commit [OK]

Common Mistakes:

• Squashing commits in wrong order
• Not moving last commit to first position
• Using squash on wrong commits