Yes - it's pretty opaque to trace through, but you can see in `valid` that for a given move history, a "good" test is performed on each instruction in the assembly listing - a full pass. This is invoked, asymptotically at least, once per jump per level of the search tree explored in `bigotimes`. Each level 'i' of the search tree has a history of `i` jumps decided to be short or near and branches 'n-i' times; both of those average out to n/2, so the tree searches n^2 nodes with each node doing 'n' iterations over the list of instructions to check all jumps are valid, so the total running time is O(n^3).
(With some modifications to the code as shown, anyway: `lookup` is linear but used in such a way it can be replaced with a constant vector index, instruction lists can be compressed to just jumps & labels with byte counts following, avoiding the duplicate invocations of `p` in `arginf`, etc).
I'd be dubious that there's an algorithm to find the true minimum in less than cubic time, but there's plenty of "good enough" approaches: most branches will be definitely short or definitely not; jumps backwards can be resolved when encountered; jumps forward can be written long and replaced with a short jump plus no-op padding when the target is encountered within short jump distance.
(With some modifications to the code as shown, anyway: `lookup` is linear but used in such a way it can be replaced with a constant vector index, instruction lists can be compressed to just jumps & labels with byte counts following, avoiding the duplicate invocations of `p` in `arginf`, etc).
I'd be dubious that there's an algorithm to find the true minimum in less than cubic time, but there's plenty of "good enough" approaches: most branches will be definitely short or definitely not; jumps backwards can be resolved when encountered; jumps forward can be written long and replaced with a short jump plus no-op padding when the target is encountered within short jump distance.