Recovering from bad rebase in Git - Time & Space Complexity

Time Complexity: Recovering from bad rebase

O(n)

Understanding Time Complexity

When recovering from a bad rebase in git, we want to understand how the time to fix the problem grows as the number of commits involved increases.

We ask: How does the effort to undo or fix a rebase scale with the number of commits?

Scenario Under Consideration

Analyze the time complexity of the following git commands used to recover from a bad rebase.

git reflog
# Find the commit before the bad rebase

git reset --hard <commit-hash>
# Reset branch to that commit

# Optionally, reapply changes carefully

This snippet shows how to find the safe commit and reset the branch to undo the bad rebase.

Identify Repeating Operations

Look for repeated steps or operations that grow with input size.

• Primary operation: Scanning the reflog entries to find the correct commit.
• How many times: Number of reflog entries equals number of recent commits and actions.

How Execution Grows With Input

The time to find the right commit grows as the number of commits in reflog grows.

Input Size (n)	Approx. Operations
10 commits	Scan about 10 reflog entries
100 commits	Scan about 100 reflog entries
1000 commits	Scan about 1000 reflog entries

Pattern observation: The effort grows linearly with the number of commits you check.

Final Time Complexity

Time Complexity: O(n)

This means the time to recover grows in direct proportion to the number of commits you need to review.

Common Mistake

[X] Wrong: "Resetting after a bad rebase is instant no matter how many commits there are."

[OK] Correct: You must find the correct commit in the reflog, which takes longer if there are many commits to check.

Interview Connect

Understanding how recovery steps scale helps you explain your troubleshooting approach clearly and shows you grasp practical git workflows.

Self-Check

"What if you used git reflog with a filter or limit? How would that affect the time complexity of finding the right commit?"

Practice

1. What is the safest way to stop a rebase process if you realize it is going wrong?

easy

A. Use git rebase --abort to cancel the rebase

B. Use git reset --hard HEAD to cancel the rebase

C. Use git commit --amend to fix the rebase

D. Use git push --force to undo the rebase

Solution

1. Step 1: Understand the rebase abort command

   The command git rebase --abort safely stops and cancels the ongoing rebase process, restoring the branch to its original state before the rebase started.

2. Step 2: Compare with other commands

   Other commands like git reset --hard HEAD or git commit --amend do not cancel a rebase safely. git push --force is for pushing changes, not aborting rebase.

3. Final Answer:

   Use git rebase --abort to cancel the rebase -> Option A

4. Quick Check:

   Cancel rebase safely = git rebase --abort [OK]

Hint: Abort rebase with git rebase --abort to safely cancel [OK]

Common Mistakes:

• Using git reset --hard HEAD which may lose changes
• Trying to amend commits during rebase to fix errors
• Forcing push without fixing rebase issues

2. Which of the following commands correctly shows the history of recent HEAD positions to help recover from a bad rebase?

easy

A. git reflog

B. git branch -a

C. git status

D. git log --oneline

Solution

1. Step 1: Identify the command to view HEAD history

   git reflog shows a log of where HEAD and branches have pointed recently, including before and after rebases.

2. Step 2: Understand why other commands don't help here

   git log --oneline shows commit history but not HEAD movements. git status shows current state. git branch -a lists branches.

3. Final Answer:

   git reflog -> Option A

4. Quick Check:

   View HEAD history = git reflog [OK]

Hint: Use git reflog to find commits before rebase [OK]

Common Mistakes:

• Using git log which doesn't show HEAD moves
• Confusing git status with reflog
• Looking at branches instead of commit history

3. After a bad rebase, you find the commit hash abc1234 from git reflog. What does the command git reset --hard abc1234 do?

medium

A. Creates a new branch at commit abc1234

B. Moves the current branch to commit abc1234 and discards all changes after it

C. Starts a new rebase from commit abc1234

D. Shows the differences between HEAD and abc1234

Solution

1. Step 1: Understand git reset --hard with a commit

   The command git reset --hard abc1234 moves the current branch pointer to the commit abc1234 and resets the working directory and index to match that commit, discarding any changes after it.

2. Step 2: Clarify what the other options do not do

   This command does not create a new branch, start a rebase, or show differences. It forcibly resets the branch state.

3. Final Answer:

   Moves branch to abc1234 and discards later changes -> Option B

4. Quick Check:

   Reset hard to commit = move branch and discard changes [OK]

Hint: Reset hard to commit to undo bad rebase changes [OK]

Common Mistakes:

• Thinking reset creates a new branch
• Confusing reset with diff or rebase commands
• Using reset without knowing it discards changes

4. You started a rebase but got conflicts and want to cancel it. You run git reset --hard HEAD instead of git rebase --abort. What is the likely result?

medium

A. The rebase is safely canceled and branch restored

B. The rebase continues but changes are lost

C. The working directory resets but rebase metadata remains, causing issues

D. Git shows an error and stops

Solution

1. Step 1: Understand difference between reset and rebase abort

   git reset --hard HEAD resets files but does not clear rebase state files, so the rebase process is still active.

2. Step 2: Consequence of not aborting rebase properly

   This causes Git to think rebase is ongoing, leading to confusion and possible errors until git rebase --abort is run.

3. Final Answer:

   Working directory resets but rebase metadata remains, causing issues -> Option C

4. Quick Check:

   Reset hard ≠ abort rebase; rebase metadata stays [OK]

Hint: Always use git rebase --abort to cancel rebase, not reset [OK]

Common Mistakes:

• Using reset hard to cancel rebase
• Assuming reset clears rebase state
• Ignoring rebase metadata files causing errors

5. You performed a bad rebase and want to recover your branch to the state before the rebase started. Which sequence of commands correctly recovers your branch?

hard

A. git checkout master -> git merge --abort

B. git reset --hard HEAD~1 -> git rebase --abort

C. git rebase --continue -> git reset --soft HEAD~1

D. git reflog -> find commit before rebase -> git reset --hard <commit>

Solution

1. Step 1: Use git reflog to find the commit before the bad rebase

   git reflog lists recent HEAD positions, so you can identify the commit hash before the rebase started.

2. Step 2: Reset branch to that commit to undo the bad rebase

   Using git reset --hard <commit> moves the branch pointer back and resets files to that safe commit, effectively undoing the bad rebase.

3. Final Answer:

   git reflog -> find commit before rebase -> git reset --hard <commit> -> Option D

4. Quick Check:

   Recover bad rebase = reflog + reset hard [OK]

Hint: Find pre-rebase commit with reflog, then reset hard to it [OK]

Common Mistakes:

• Trying to abort after rebase finished
• Using reset soft which keeps changes
• Confusing merge abort with rebase abort