Bisect for finding bug-introducing commits in Git - Time & Space Complexity

Time Complexity: Bisect for finding bug-introducing commits

O(log n)

Understanding Time Complexity

When using git bisect, we want to find which commit introduced a bug efficiently.

We ask: How does the number of steps grow as the number of commits increases?

Scenario Under Consideration

Analyze the time complexity of this git bisect process.

git bisect start
# mark bad commit
git bisect bad
# mark good commit
git bisect good <commit-hash>
# git automatically checks out middle commit
# user tests and marks commit as good or bad
# repeat until bug-introducing commit is found
    

This code snippet shows the basic steps of starting bisect, marking commits, and testing to find the bad commit.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking out and testing the middle commit in the current range.
• How many times: About log base 2 of the number of commits between good and bad.

How Execution Grows With Input

Each step halves the number of commits left to check.

Input Size (n commits)	Approx. Steps (tests)
10	4
100	7
1000	10

Pattern observation: The number of steps grows slowly, roughly doubling input size adds only one extra step.

Final Time Complexity

Time Complexity: O(log n)

This means the number of tests grows slowly as the number of commits grows, making bisect efficient.

Common Mistake

[X] Wrong: "Git bisect checks every commit one by one, so it takes as many steps as commits."

[OK] Correct: Git bisect uses a smart divide-and-conquer method, cutting the search space in half each time, so it needs far fewer steps.

Interview Connect

Understanding how bisect works shows you can analyze efficient search methods, a useful skill in many tech tasks.

Self-Check

"What if the commits are not in a straight line but in multiple branches? How would that affect the bisect time complexity?"

Practice

1. What is the main purpose of git bisect?

easy

A. To delete old commits from history

B. To merge two branches automatically

C. To create a new branch from the current commit

D. To find the first commit that introduced a bug

Solution

1. Step 1: Understand the role of git bisect

   Git bisect helps identify which commit introduced a bug by testing commits between a known good and a bad commit.

2. Step 2: Compare with other git commands

   Merging branches, deleting commits, or creating branches are different git operations unrelated to bisect.

3. Final Answer:

   To find the first commit that introduced a bug -> Option D

4. Quick Check:

   git bisect = find bug commit [OK]

Hint: Bisect narrows down bug commit by testing between good and bad [OK]

Common Mistakes:

• Confusing bisect with merge or branch commands
• Thinking bisect deletes commits
• Assuming bisect creates branches

2. Which command correctly starts a bisect session assuming HEAD is bad and v1.0 is good?

easy

A. git bisect start v1.0 HEAD

B. git bisect start HEAD v1.0

C. git bisect begin HEAD v1.0

D. git bisect init v1.0 HEAD

Solution

1. Step 1: Recall git bisect start syntax

   The correct syntax is git bisect start <bad> <good>, where the first argument is the bad commit and the second is the good commit.

2. Step 2: Match the given commits

   Since HEAD is bad and v1.0 is good, the command is git bisect start HEAD v1.0.

3. Final Answer:

   git bisect start HEAD v1.0 -> Option B

4. Quick Check:

   git bisect start bad good = start [OK]

Hint: Start bisect with bad commit first, then good commit [OK]

Common Mistakes:

• Reversing good and bad commits in the command
• Using incorrect command like bisect begin or init
• Omitting the start keyword

3. Given this bisect session output:

Bisecting: 3 revisions left to test after this (roughly 2 steps)
Testing commit abc1234

If you run git bisect good and then git bisect bad on the next commit, what will git do next?

medium

A. Git will narrow down the range and checkout the next commit to test

B. Git will end the bisect session immediately

C. Git will reset to the original branch without changes

D. Git will throw an error because you cannot mark good then bad consecutively

Solution

1. Step 1: Understand bisect workflow

   Marking commits as good or bad tells git which side of the commit range to keep searching. After marking, git checks out the next commit to test.

2. Step 2: Analyze the given commands

   Marking one commit good, then the next bad, narrows the search range. Git continues bisecting until it finds the first bad commit.

3. Final Answer:

   Git will narrow down the range and checkout the next commit to test -> Option A

4. Quick Check:

   Mark good/bad -> git picks next commit [OK]

Hint: Mark commits good/bad to let git pick next test commit [OK]

Common Mistakes:

• Thinking bisect ends after one good and one bad mark
• Assuming git resets automatically after marking
• Believing marking good then bad consecutively causes error

4. You started a bisect session but accidentally marked a good commit as bad. What is the best way to fix this?

medium

A. Edit the .git/BISECT_LOG file manually to fix the mistake

B. Run git bisect skip on the wrong commit

C. Run git bisect good on the same commit to correct it

D. Run git bisect reset and start over

Solution

1. Step 1: Understand bisect marking correction

   Git bisect allows re-marking a commit to correct its status if marked incorrectly.

2. Step 2: Correct the marking

   Run git bisect good on the commit you accidentally marked as bad to update the bisect state.

3. Final Answer:

   Run git bisect good on the same commit to correct it -> Option C

4. Quick Check:

   Re-mark good/bad to correct [OK]

Hint: Re-mark the commit with git bisect good to fix [OK]

Common Mistakes:

• Thinking you must reset instead of re-marking
• Editing internal git files manually
• Using skip to fix a marking error

5. You have a large project with 1000 commits. You know commit abc123 is good and def456 is bad. You want to find the first bad commit using git bisect. Which sequence of commands correctly performs this task?

hard

A. git bisect start def456 abc123; git bisect bad def456; git bisect good abc123; test commits; git bisect reset

B. git bisect start abc123 def456; git bisect bad abc123; git bisect good def456; test commits; git bisect reset

C. git bisect start def456 abc123; git bisect good def456; git bisect bad abc123; test commits; git bisect reset

D. git bisect start abc123 def456; git bisect good def456; git bisect bad abc123; test commits; git bisect reset

Solution

1. Step 1: Start bisect with bad then good commit

   The correct syntax is git bisect start <bad> <good>. Since def456 is bad and abc123 is good, the command is git bisect start def456 abc123.

2. Step 2: Mark the known commits correctly

   Mark the bad commit with git bisect bad def456 and the good commit with git bisect good abc123. Then test intermediate commits as git suggests.

3. Step 3: Finish bisect session

   After finding the first bad commit, run git bisect reset to return to the original branch.

4. Final Answer:

   git bisect start def456 abc123; git bisect bad def456; git bisect good abc123; test commits; git bisect reset -> Option A

5. Quick Check:

   Start with bad then good, mark correctly, reset [OK]

Hint: Start bisect with bad then good commit, mark accordingly [OK]

Common Mistakes:

• Reversing good and bad commits in start command
• Marking commits with wrong status
• Skipping reset after bisect finishes