Finding a set of mututally orthogonal vectors. For a given sparsity, after a large enough dimention, two randomly chosen vector will almost always be orthogonal.
That would be a case of higher probability of finding a solution in one step.
But the solution would still need to be checked and another candidates generated until a solution is found.
Average time would be minimized by generating random vectors each time.
But that would increase the worst case to unbounded (effectively infinite) time since an increasingly vanishingly small but finite chance that a solution has not yet been found will exist after any number of steps.
Some kind of simple search would be vastly more bounded, but in practice require more computation.
But the solution would still need to be checked and another candidates generated until a solution is found.
Average time would be minimized by generating random vectors each time.
But that would increase the worst case to unbounded (effectively infinite) time since an increasingly vanishingly small but finite chance that a solution has not yet been found will exist after any number of steps.
Some kind of simple search would be vastly more bounded, but in practice require more computation.