Recovering deleted branches in Git - Time & Space Complexity

Time Complexity: Recovering deleted branches

O(n)

Understanding Time Complexity

When recovering deleted branches in git, we want to know how the time to find and restore a branch changes as the repository grows.

How does git search through its history to recover a branch?

Scenario Under Consideration

Analyze the time complexity of this git command sequence.

# Find the commit hash of the deleted branch
git reflog

# Create a new branch at that commit
git branch recovered-branch <commit-hash>
    

This code finds the commit where the deleted branch pointed and recreates the branch there.

Identify Repeating Operations

Look for repeated steps that take time as input grows.

• Primary operation: Scanning the reflog entries to find the commit hash.
• How many times: Once per reflog entry, which grows with the number of recent git actions.

How Execution Grows With Input

As the number of reflog entries grows, git scans more entries to find the commit.

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

Pattern observation: The time grows roughly in direct proportion to the number of reflog entries.

Final Time Complexity

Time Complexity: O(n)

This means the time to recover a deleted branch grows linearly with the number of reflog entries git must check.

Common Mistake

[X] Wrong: "Recovering a deleted branch is instant no matter how big the repo is."

[OK] Correct: Git must scan reflog entries one by one, so more history means more time to find the right commit.

Interview Connect

Understanding how git searches history helps you reason about performance in real projects and shows you can think about tool behavior beyond just commands.

Self-Check

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

Practice

1. What is the primary Git command used to find the commit hash of a recently deleted branch?

easy

A. git reflog

B. git branch -d

C. git reset --hard

D. git merge

Solution

1. Step 1: Understand the purpose of git reflog

   git reflog records all changes to the HEAD, including deleted branches.

2. Step 2: Identify the command that shows commit history including deleted refs

   git reflog lets you find the commit hash of the deleted branch.

3. Final Answer:

   git reflog -> Option A

4. Quick Check:

   Find deleted branch commit = git reflog [OK]

Hint: Use git reflog to find lost commits fast [OK]

Common Mistakes:

• Confusing git branch -d as recovery command
• Using git reset --hard which discards changes
• Thinking git merge recovers deleted branches

2. Which of the following commands correctly recreates a deleted branch named feature1 from a commit hash abc1234 and switches to it?

easy

A. git checkout -b feature1 abc1234

B. git reset feature1 abc1234

C. git branch feature1 abc1234

D. git checkout abc1234 feature1

Solution

1. Step 1: Understand the syntax to create a branch at a commit

   The correct syntax is git checkout -b [branch] [commit] to create and switch.

2. Step 2: Identify the correct command

   git checkout -b feature1 abc1234 creates branch feature1 at commit abc1234.

3. Final Answer:

   git checkout -b feature1 abc1234 -> Option A

4. Quick Check:

   Create branch at commit = git checkout -b branch commit [OK]

Hint: Use git checkout -b branch commit to restore branch [OK]

Common Mistakes:

• Using git checkout commit branch without -b
• Using git reset which does not create branches
• Using git branch without switching

3. After deleting a branch bugfix, you run git reflog and see this entry:

abc1234 HEAD@{2}: checkout: moving from bugfix to main

Which command will correctly restore the bugfix branch at that commit?

medium

A. git checkout bugfix

B. git branch -d bugfix abc1234

C. git reset --hard abc1234

D. git checkout -b bugfix abc1234

Solution

1. Step 1: Identify commit hash from reflog

   The commit hash abc1234 is where bugfix was last checked out.

2. Step 2: Use command to recreate branch at that commit

   git checkout -b bugfix abc1234 creates and switches to bugfix at that commit.

3. Final Answer:

   git checkout -b bugfix abc1234 -> Option D

4. Quick Check:

   Restore branch from commit = git checkout -b branch commit [OK]

Hint: Use reflog commit hash with git checkout -b [OK]

Common Mistakes:

• Using git branch -d which deletes branches
• Using git reset --hard which resets HEAD but not branches
• Trying git checkout bugfix without recreating branch

4. You tried to recover a deleted branch using git checkout -b feature abc123 but got an error: fatal: A branch named 'feature' already exists.
What is the best way to fix this?

medium

A. Use git checkout feature to switch to the existing branch

B. Delete the existing branch first with git branch -D feature then retry

C. Use git branch -b feature abc123 instead

D. Rename the commit hash to a new one

Solution

1. Step 1: Understand the error

   The error means branch feature already exists locally.

2. Step 2: Delete existing branch to recreate

   Use git branch -D feature to force delete the existing branch, then recreate it.

3. Final Answer:

   Delete existing branch with git branch -D feature then retry -> Option B

4. Quick Check:

   Delete conflicting branch before recreate [OK]

Hint: Delete existing branch with -D before recreating [OK]

Common Mistakes:

• Trying git branch -b which is invalid syntax
• Ignoring the existing branch and forcing checkout
• Renaming commit hash which is not possible

5. You accidentally deleted a branch release and want to recover it. You run git reflog and find multiple commits related to release. Which sequence of commands correctly recovers the branch at the latest commit and deletes the old branch pointer?

hard

A. git checkout -b release

B. git checkout release; git reset --hard

C. git branch -D release; git checkout -b release

D. git branch release

Solution

1. Step 1: Delete any existing branch pointer named release

   Use git branch -D release to remove old or conflicting branch references.

2. Step 2: Create a new branch release at the desired commit

   Use git checkout -b release <commit-hash> to recreate and switch to the branch at the correct commit.

3. Final Answer:

   git branch -D release; git checkout -b release <commit-hash> -> Option C

4. Quick Check:

   Delete old branch then recreate at commit [OK]

Hint: Delete old branch first, then recreate at commit [OK]

Common Mistakes:

• Using git checkout release when branch is deleted
• Using git reset --hard without recreating branch
• Using git branch release without switching