Assume that a node A in the commit tree of a codebase contains a bug but some ancestor B of A is clean from that very bug. Given the topology of the commit tree [B,A] leading from B to A, can we predict c the maximum number of steps needed to locate the commit where the bug appeared, in terms of number of vertices, arrows, merges or cycles and other simple graph invariants?There is two easy cases:If the history from B to A is linear, then c is the binary logarithm of the number of nodes between B and A.If the history is totally parallel, i.e. a family of independent commits A  M  B, then c is the number of such commits.From the two examples, we learn that linear history leads to cheaper bisection processes, but can we be more precise than this?  It is easy to write a program to compute c  which I still haven't done yet  but I am looking for a pretty algebraic formula. If the problem is hard, it could be interesting and easier to have expected value of c given, for instance, the number of vertices, arrows and merges, or something similar.
What is the maximum number of steps to find a bug using bisecting?
graph;scm