Recovering from hard reset in Git - Time & Space Complexity

Time Complexity: Recovering from hard reset

O(n)

Understanding Time Complexity

When recovering from a hard reset in git, it's important to understand how the time to recover grows as the number of commits or changes increases.

We want to know how the effort to find and restore lost commits scales with the size of the commit history.

Scenario Under Consideration

Analyze the time complexity of the following git commands used to recover lost commits after a hard reset.

# List all reflog entries
$ git reflog

# Find the commit hash before reset
$ git checkout <commit-hash>

# Create a new branch to save the commit
$ git branch recovery-branch

# Switch back to main branch
$ git checkout main

# Reset main branch to recovered commit
$ git reset --hard recovery-branch
    

This sequence helps find and restore commits lost after a hard reset by using the reflog and resetting branches.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning the reflog entries to find the commit before the reset.
• How many times: The reflog is traversed once, but its size depends on the number of recent commits and actions.

How Execution Grows With Input

The time to scan reflog entries grows as the number of recorded commits and actions increases.

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

Pattern observation: The time grows linearly with the number of reflog entries scanned.

Final Time Complexity

Time Complexity: O(n)

This means the time to recover grows in direct proportion to the number of reflog entries you need to check.

Common Mistake

[X] Wrong: "Recovering lost commits after a hard reset is instant regardless of history size."

[OK] Correct: The recovery depends on scanning the reflog, which grows with your commit history and actions, so it takes longer if there are many entries.

Interview Connect

Understanding how git operations scale helps you explain your troubleshooting approach clearly and shows you grasp practical version control challenges.

Self-Check

"What if we used git fsck to find dangling commits instead of reflog? How would the time complexity change?"

Practice

1. What is the primary command to view the history of recent commits and actions in Git after a hard reset?

easy

A. git status

B. git log --oneline

C. git reflog

D. git reset --soft

Solution

1. Step 1: Understand the purpose of git reflog

   git reflog shows a log of all recent commits and HEAD movements, including resets.

2. Step 2: Compare with other commands

   git log --oneline shows commit history but not HEAD changes; git status shows current state; git reset --soft changes HEAD but does not show history.

3. Final Answer:

   git reflog -> Option C

4. Quick Check:

   View recent HEAD changes = git reflog [OK]

Hint: Use git reflog to see all recent HEAD changes [OK]

Common Mistakes:

• Confusing git log with git reflog
• Using git status to find past commits
• Thinking git reset shows history

2. Which of the following is the correct syntax to reset your Git repository to a previous commit with a hard reset?

easy

A. git reset --hard <commit>

B. git reset -soft <commit>

C. git checkout --hard <commit>

D. git revert --hard <commit>

Solution

1. Step 1: Identify the correct reset syntax

   The correct command to reset to a previous commit and discard changes is git reset --hard <commit>.

2. Step 2: Eliminate incorrect options

   -soft is invalid flag, git checkout --hard is not a valid command, and git revert does not accept --hard.

3. Final Answer:

   git reset --hard <commit> -> Option A

4. Quick Check:

   Hard reset syntax = git reset --hard [OK]

Hint: Use git reset --hard commit_hash to restore state [OK]

Common Mistakes:

• Using -soft instead of --hard
• Confusing git revert with reset
• Trying git checkout with --hard

3. After running git reset --hard HEAD~2, which command will help you find the commit hash to recover your lost changes?

medium

A. git status

B. git branch

C. git diff

D. git reflog

Solution

1. Step 1: Understand what git reset --hard HEAD~2 does

   This command moves HEAD back two commits and discards changes, potentially losing recent commits from view.

2. Step 2: Identify command to find lost commit hashes

   git reflog shows all recent HEAD positions including those before the reset, allowing recovery.

3. Final Answer:

   git reflog -> Option D

4. Quick Check:

   Find lost commits after reset = git reflog [OK]

Hint: Use git reflog to find lost commit hashes after reset [OK]

Common Mistakes:

• Using git status which shows current state only
• Using git branch which lists branches, not commits
• Using git diff which shows changes, not history

4. You accidentally ran git reset --hard HEAD~1 and lost your latest commit. Which sequence of commands will help you recover it?

medium

A. git reflog to find commit hash, then git reset --hard <hash>

B. git log to find commit, then git revert HEAD

C. git checkout HEAD~1 then git commit --amend

D. git reset --soft HEAD~1 then git commit

Solution

1. Step 1: Use git reflog to find lost commit hash

   git reflog lists all recent HEAD positions including the lost commit before reset.

2. Step 2: Reset hard to the lost commit hash

   Use git reset --hard <hash> to restore the repository to that commit state.

3. Final Answer:

   git reflog then git reset --hard <hash> -> Option A

4. Quick Check:

   Recover lost commit = reflog + reset --hard [OK]

Hint: Find commit with reflog, restore with reset --hard [OK]

Common Mistakes:

• Using git log which may not show lost commits
• Trying git revert which creates new commits
• Using reset --soft after hard reset without commit hash

5. You performed a hard reset to a commit two steps behind but realize you need to recover the lost commits and keep your current changes. What is the best approach?

hard

A. Run git reset --hard HEAD@{1} to go back to previous HEAD state

B. Use git reflog to find lost commits, then git cherry-pick them onto current branch

C. Use git revert on the reset commit to undo the reset

D. Create a new branch from HEAD~2 and merge it back

Solution

1. Step 1: Find lost commits using git reflog

   git reflog shows the commit hashes that were lost after the hard reset.

2. Step 2: Use git cherry-pick to apply lost commits onto current branch

   This preserves current changes and reapplies lost commits without resetting the branch.

3. Final Answer:

   Use git reflog and cherry-pick lost commits -> Option B

4. Quick Check:

   Recover lost commits without losing current changes = reflog + cherry-pick [OK]

Hint: Cherry-pick lost commits found via reflog to keep current work [OK]

Common Mistakes:

• Using reset --hard to go back loses current changes
• Using revert on reset commit does not restore lost commits
• Merging from old branch may cause conflicts or duplicate commits