Reordering commits in Git - Time & Space Complexity

Time Complexity: Reordering commits

O(n)

Understanding Time Complexity

When we reorder commits in git, we want to know how the time needed changes as the number of commits grows.

We ask: How does the effort to reorder commits grow when we have more commits?

Scenario Under Consideration

Analyze the time complexity of the following git commands used to reorder commits.

git rebase -i HEAD~5
# Opens editor to reorder last 5 commits
# User changes order and saves
# Git applies commits in new order

This snippet shows an interactive rebase to reorder the last 5 commits by rewriting history.

Identify Repeating Operations

Look for repeated steps in the rebase process.

• Primary operation: Git applies each commit one by one in the new order.
• How many times: Once for each commit being reordered (n times).

How Execution Grows With Input

As the number of commits to reorder grows, git applies more commits sequentially.

Input Size (n)	Approx. Operations
5	5 commit applications
50	50 commit applications
500	500 commit applications

Pattern observation: The work grows directly with the number of commits to reorder.

Final Time Complexity

Time Complexity: O(n)

This means the time to reorder commits grows linearly with how many commits you reorder.

Common Mistake

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

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

Interview Connect

Understanding how git operations scale helps you explain your workflow choices clearly and shows you know how tools behave with bigger projects.

Self-Check

"What if we reorder only a subset of commits instead of all recent ones? How would the time complexity change?"

Practice

1. What is the main purpose of using git rebase -i when working with commits?

easy

A. To create a new branch from the current commit

B. To reorder, edit, or squash commits interactively

C. To merge two branches automatically

D. To delete the entire commit history

Solution

1. Step 1: Understand the function of git rebase -i

   This command opens an interactive editor allowing you to reorder, edit, or squash commits.

2. Step 2: Compare with other options

   Creating branches, merging, or deleting history are not the main purposes of this command.

3. Final Answer:

   To reorder, edit, or squash commits interactively -> Option B

4. Quick Check:

   Interactive rebase = reorder commits [OK]

Hint: Use interactive rebase to reorder commits easily [OK]

Common Mistakes:

• Confusing rebase with branch creation
• Thinking rebase deletes history
• Mixing rebase with merge commands

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 other options for syntax errors

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

3. Final Answer:

   git rebase -i HEAD~3 -> Option A

4. Quick Check:

   Use HEAD~N for last N commits [OK]

Hint: Use HEAD~N to specify last N commits in rebase [OK]

Common Mistakes:

• Using caret (^) incorrectly for commit range
• Omitting the number after ~
• Confusing HEAD~ with HEAD^

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
pick a1b2c3 Commit A
pick 789abc Commit C

What will be the order of commits after the rebase?

medium

A. Commit B, Commit A, Commit C

B. Commit A, Commit B, Commit C

C. Commit C, Commit B, Commit A

D. Commit A, Commit C, Commit B

Solution

1. Step 1: Understand the todo list order

   The interactive rebase applies commits in the order listed. Changing the order changes commit history order.

2. Step 2: Apply the new order

   New order is Commit B, then Commit A, then Commit C.

3. Final Answer:

   Commit B, Commit A, Commit C -> Option A

4. Quick Check:

   Rebase applies commits in listed order [OK]

Hint: Order commits in todo list to reorder history [OK]

Common Mistakes:

• Assuming original order stays after rebase
• Confusing commit hashes with order
• Ignoring the todo list sequence

4. You ran git rebase -i HEAD~3 and changed the order of commits, but Git shows a conflict error. What is the best way to fix this?

medium

A. Force push the branch without resolving conflicts

B. Abort the rebase with git rebase --abort and try again

C. Delete the .git folder and start over

D. Manually resolve conflicts, then run git rebase --continue

Solution

1. Step 1: Understand rebase conflict handling

   When conflicts occur during rebase, you must manually fix them in files.

2. Step 2: Continue rebase after resolving conflicts

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

3. Final Answer:

   Manually resolve conflicts, then run git rebase --continue -> Option D

4. Quick Check:

   Fix conflicts + git rebase --continue [OK]

Hint: Fix conflicts, then continue rebase with git rebase --continue [OK]

Common Mistakes:

• Ignoring conflicts and force pushing
• Aborting rebase without trying to fix
• Deleting .git folder which loses repo data

5. You want to reorder the last 4 commits to put the oldest commit last without changing their content. Which sequence of commands correctly achieves this?

hard

A. Run git reset --hard HEAD~4 then cherry-pick commits in new order

B. Run git merge --reorder HEAD~4 to reorder commits automatically

C. Run git rebase -i HEAD~4, then move the first commit line to the bottom in the editor

D. Run git rebase -i HEAD~3 and swap the last two commits

Solution

1. Step 1: Use interactive rebase on last 4 commits

   Running git rebase -i HEAD~4 opens the last 4 commits for editing order.

2. Step 2: Move the oldest commit line to the bottom

   In the editor, reorder lines so the oldest commit is last, preserving content.

3. Final Answer:

   Run git rebase -i HEAD~4, then move the first commit line to the bottom in the editor -> Option C

4. Quick Check:

   Interactive rebase + reorder lines = reorder commits [OK]

Hint: Use interactive rebase and reorder lines to change commit order [OK]

Common Mistakes:

• Using reset which loses commit history
• Trying non-existent git merge --reorder command
• Using wrong commit range in rebase