Reflog for finding lost commits in Git - Time & Space Complexity

Time Complexity: Reflog for finding lost commits

O(n)

Understanding Time Complexity

When using git reflog to find lost commits, we want to know how long it takes to search through the history of changes.

We ask: How does the time to find a commit grow as the number of reflog entries increases?

Scenario Under Consideration

Analyze the time complexity of this git reflog command sequence.

git reflog
# Lists all recent HEAD changes

git show HEAD@{5}
# Shows the commit at position 5 in reflog

# Searching reflog for a commit by message or hash
git reflog | grep 'fix bug'

This code lists reflog entries and searches for a specific commit by scanning the list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each reflog entry one by one.
• How many times: Once for each reflog entry, from the newest to the oldest.

How Execution Grows With Input

As the number of reflog entries grows, the time to scan them grows too.

Input Size (n)	Approx. Operations
10	10 scans
100	100 scans
1000	1000 scans

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

Final Time Complexity

Time Complexity: O(n)

This means the time to find a commit grows linearly with the number of reflog entries.

Common Mistake

[X] Wrong: "Searching reflog is instant no matter how many entries there are."

[OK] Correct: Each reflog entry must be checked one by one, so more entries mean more time.

Interview Connect

Understanding how git commands scale helps you explain your problem-solving skills clearly and confidently.

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?

easy

A. To list all remote branches

B. To permanently delete commits from the repository

C. To record where HEAD and branches have pointed recently

D. To merge two branches automatically

Solution

1. Step 1: Understand what reflog tracks

   Reflog records the history of where HEAD and branch references have pointed, including commits that might be lost after resets or rebases.

2. Step 2: Compare options with reflog purpose

   Only To record where HEAD and branches have pointed recently correctly describes reflog's role. Options B, C, and D describe unrelated git functions.

3. Final Answer:

   To record where HEAD and branches have pointed recently -> Option C

4. Quick Check:

   Reflog tracks HEAD history = A [OK]

Hint: Reflog shows recent HEAD moves, like a safety net [OK]

Common Mistakes:

• Confusing reflog with git log
• Thinking reflog deletes commits
• Assuming reflog lists remote branches

2. Which command correctly shows the reflog entries?

easy

A. git reflog

B. git reflog list

C. git reflog -a

D. git reflog --show

Solution

1. Step 1: Recall the basic reflog command

   The simplest and correct command to show reflog entries is git reflog.

2. Step 2: Evaluate other options

   git reflog --show is invalid; git reflog list and git reflog -a are invalid commands.

3. Final Answer:

   git reflog -> Option A

4. Quick Check:

   Basic reflog command = git reflog [OK]

Hint: Use just 'git reflog' to see recent HEAD moves [OK]

Common Mistakes:

• Adding unnecessary subcommands like 'list'
• Using invalid flags like '-a'
• Confusing reflog with git log

3. After running git reset --hard HEAD~1, you realize you lost a commit. Which command helps you find the lost commit's hash?

medium

A. git reflog

B. git status

C. git branch

D. git log --oneline

Solution

1. Step 1: Understand what happens after reset

   git reset --hard HEAD~1 moves HEAD back one commit, making the latest commit unreachable but still in reflog.

2. Step 2: Identify command to find lost commit

   git reflog shows recent HEAD positions including the lost commit's hash. Other commands won't show unreachable commits.

3. Final Answer:

   git reflog -> Option A

4. Quick Check:

   Reflog shows lost commits after reset = C [OK]

Hint: Use reflog to find commits lost by reset [OK]

Common Mistakes:

• Using git status which shows working tree only
• Using git branch which lists branches, not commits
• Using git log which hides unreachable commits

4. You ran git reset --hard HEAD~2 but want to restore the latest commit. Which command correctly resets to the lost commit using reflog?

medium

A. git reset --hard HEAD@{2}

B. git reset --hard origin/main

C. git reset --hard HEAD~1

D. git reset --hard HEAD@{1}

Solution

1. Step 1: Understand reflog indexing

   After resetting HEAD back two commits, reflog entries show HEAD@{0} as current, HEAD@{1} as previous position (the lost commit), and HEAD@{2} as older.

2. Step 2: Choose correct reflog entry to restore

   To restore the latest lost commit, reset to HEAD@{1} which points to it. HEAD@{2} is older, HEAD~1 is relative to current HEAD, and origin/main may differ.

3. Final Answer:

   git reset --hard HEAD@{1} -> Option D

4. Quick Check:

   Use HEAD@{1} to restore last HEAD position [OK]

Hint: Reset to HEAD@{1} to undo last reset [OK]

Common Mistakes:

• Using HEAD@{2} which is older than needed
• Using HEAD~1 which is relative to current HEAD
• Resetting to origin/main which may differ

5. You accidentally deleted a branch with important commits. How can you recover the lost commits using reflog?

hard

A. Run git branch -d to restore the branch

B. Find the commit hash in git reflog and create a new branch at that hash

C. Use git reset --hard origin/branch-name to recover commits

D. Re-clone the repository to get the branch back

Solution

1. Step 1: Locate lost commits in reflog

   Deleted branch commits remain in reflog as recent HEAD positions or branch references before deletion.

2. Step 2: Create a new branch at the lost commit hash

   After finding the commit hash in reflog, use git branch new-branch-name <commit-hash> to restore the branch with lost commits.

3. Final Answer:

   Find the commit hash in git reflog and create a new branch at that hash -> Option B

4. Quick Check:

   Reflog + new branch recovers deleted commits [OK]

Hint: Use reflog hash to recreate deleted branch [OK]

Common Mistakes:

• Trying to delete branch again to restore it
• Resetting to origin which may not have deleted commits
• Re-cloning loses local lost commits