It explains runtime speeds relative to n (size of history, roughly). It doesn’t tell you whether to expect it to take 5 minutes or 5 hours, but it will tell you whether a tool will scale up to large repos or not.

An O(log n) tool will probably work fine on a large repo, an O(n^n) tool will probably have an unusable run time on anything but tiny repos.

I would generally infer that to mean “this will run in an acceptable amount of time on basically any repo”. There isn’t much of a reason to say that it’s O(log n) if it has a run time of 6 weeks when n is 1.

> An O(log n) tool will probably work fine on a large repo, an O(n^n) tool will probably have an unusable run time on anything but tiny repos.

Wouldn't all repositories in use today offer O(log n) speeds though? I would think it's a given just because search has been a solved problem for many decades now. Are there any that search at O(n^n)?

An efficient but naive approach is probably O(n), because it searches the entire history. Runtime grows as history does.

The point of bisect is that it understands each commit as a linear snapshot of the code base, to narrow down the commit that you’re looking for. So if you say that you know commit 1000 is bad and commit 1100 is good, it will ask you to check if commit 1050 is good. If 1050 is good, it knows that the bad commit has to be between 1000 and 1049 so it asks about 1025. If 1050 is bad, same thing in reverse.

A more naive approach would ask the user to check commit 1000, then 1001, then 1002, etc.

I’m honestly not well-versed enough in other version control systems to comment on whether they contain a similar feature or whether users would have to write their own.

It’s not magic that it’s O(log n) so much as that git has a native O(log n) manual search feature.