Recovering lost commits with reflog in Git - Time & Space Complexity

Time Complexity: Recovering lost commits with reflog

O(n)

Understanding Time Complexity

When using git reflog to recover lost commits, it's important to understand how the time to find a commit grows as the reflog grows.

We want to know how the number of steps changes when the reflog has more entries.

Scenario Under Consideration

Analyze the time complexity of the following git commands.

git reflog
# shows list of recent HEAD changes

git checkout <commit-hash>
# moves to the lost commit

# or

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

This code shows how to list recent commits and recover a lost commit by checking it out or resetting.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning the reflog entries to find the target commit.
• How many times: The reflog is scanned entry by entry until the commit is found.

How Execution Grows With Input

As the number of reflog entries grows, the time to find a commit grows roughly in direct proportion.

Input Size (n)	Approx. Operations
10	About 10 entries scanned
100	About 100 entries scanned
1000	About 1000 entries scanned

Pattern observation: The time grows linearly as the reflog size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to find a lost commit grows in direct proportion to the number of reflog entries.

Common Mistake

[X] Wrong: "git reflog instantly finds any commit no matter how many entries there are."

[OK] Correct: The reflog is a list scanned from newest to oldest, so more entries mean more scanning time.

Interview Connect

Understanding how git commands scale with data size shows you think about efficiency and system behavior, a valuable skill in real projects.

Self-Check

"What if git stored reflog entries in a database with indexes? How would the time complexity change?"

Practice

1. What is the primary purpose of git reflog in Git?

easy

A. To show a log of where HEAD and branch references have been recently

B. To permanently delete commits from the repository

C. To merge two branches automatically

D. To push commits to a remote repository

Solution

1. Step 1: Understand what reflog tracks

   Git reflog records changes to HEAD and branch tips, showing recent commit movements.

2. Step 2: Identify reflog's main use

   It helps find lost commits by listing recent HEAD positions, not deleting or merging.

3. Final Answer:

   To show a log of where HEAD and branch references have been recently -> Option A

4. Quick Check:

   Reflog = recent HEAD changes [OK]

Hint: Reflog shows recent HEAD moves, not branch merges or deletions [OK]

Common Mistakes:

• Confusing reflog with git log
• Thinking reflog deletes commits
• Assuming reflog pushes commits

2. Which command correctly recovers a lost commit using its reflog hash abc1234 by creating a new branch named recovered?

easy

A. git branch recovered && git checkout abc1234

B. git reset --hard recovered abc1234

C. git reflog checkout abc1234 recovered

D. git checkout -b recovered abc1234

Solution

1. Step 1: Understand how to create a branch from a commit hash

   The command git checkout -b <branch> <commit> creates and switches to a new branch at that commit.

2. Step 2: Check each option's correctness

   git checkout -b recovered abc1234 uses correct syntax. git branch recovered && git checkout abc1234 creates branch but checks out commit separately (detached HEAD). git reflog checkout abc1234 recovered is invalid syntax. git reset --hard recovered abc1234 misuses reset.

3. Final Answer:

   git checkout -b recovered abc1234 -> Option D

4. Quick Check:

   Create branch from commit: checkout -b [OK]

Hint: Use 'git checkout -b branch commit' to recover lost commit [OK]

Common Mistakes:

• Using git reflog checkout (invalid command)
• Creating branch and checkout separately causing detached HEAD
• Misusing git reset syntax

3. Given the following reflog output snippet:

abc1234 HEAD@{0}: commit: Fix typo
def5678 HEAD@{1}: commit: Add feature
789abcd HEAD@{2}: commit: Initial commit

What command will restore the commit with message 'Add feature'?

medium

A. git checkout HEAD@{2}

B. git checkout 789abcd

C. git checkout def5678

D. git checkout abc1234

Solution

1. Step 1: Identify the commit hash for 'Add feature'

   From reflog, 'Add feature' commit hash is def5678 at HEAD@{1}.

2. Step 2: Use git checkout with the correct hash

   Checking out def5678 restores that commit state.

3. Final Answer:

   git checkout def5678 -> Option C

4. Quick Check:

   Checkout commit by hash = def5678 [OK]

Hint: Match commit message to hash, then checkout that hash [OK]

Common Mistakes:

• Choosing wrong commit hash
• Using HEAD@{2} which is 'Initial commit'
• Confusing latest commit with target commit

4. You ran git reflog and found a lost commit hash abc1234. You tried git checkout abc1234 but got a detached HEAD warning. How do you fix this to recover the commit safely?

medium

A. Create a new branch at that commit using git checkout -b recovered abc1234

B. Run git reset --hard abc1234 immediately

C. Delete the reflog entry and try again

D. Push the commit hash to remote

Solution

1. Step 1: Understand detached HEAD state

   Checking out a commit hash puts you in detached HEAD, which is risky for new work.

2. Step 2: Create a branch to save the commit safely

   Use git checkout -b recovered abc1234 to create a branch and avoid losing commits.

3. Final Answer:

   Create a new branch at that commit using git checkout -b recovered abc1234 -> Option A

4. Quick Check:

   Fix detached HEAD by creating branch [OK]

Hint: Always create a branch from lost commit to avoid detached HEAD [OK]

Common Mistakes:

• Ignoring detached HEAD and continuing work
• Deleting reflog entries mistakenly
• Trying to push without branch

5. You accidentally reset your branch to an older commit, losing recent commits. You run git reflog and see:

abc1234 HEAD@{0}: reset: moving to abc1234
def5678 HEAD@{1}: commit: Add new feature
789abcd HEAD@{2}: commit: Fix bug

How do you restore your branch to include the lost 'Add new feature' commit?

hard

A. Delete reflog entries before abc1234

B. Run git reset --hard def5678 to move branch back to lost commit

C. Run git checkout abc1234 to stay at reset point

D. Run git merge def5678 from abc1234

Solution

1. Step 1: Identify lost commit hash from reflog

   The lost commit 'Add new feature' is at def5678 (HEAD@{1}).

2. Step 2: Use git reset to move branch pointer back

   Running git reset --hard def5678 restores branch to that commit, recovering lost work.

3. Final Answer:

   Run git reset --hard def5678 to move branch back to lost commit -> Option B

4. Quick Check:

   Reset branch to lost commit hash [OK]

Hint: Use git reset --hard with reflog hash to recover lost commits [OK]

Common Mistakes:

• Checking out reset commit instead of resetting branch
• Deleting reflog entries unnecessarily
• Trying to merge without branch pointer