One partial remedy for this dilemma is to modify the step-down procedure so that we keep using the old, contaminated distribution as long as it produces probability values that are within our threshold for significance. Only when the distribution begins to produce probabilities that exceed the threshold do we resort to re-computing the distribution.

Although this method is fine if all we're interested in is the binary notion of `significance', it does not suffice if we're interested in quantifying activation. It's faster than the unmodified step-down method, but still doesn't completely avoid recomputation of the null distribution, and in fact suffers from the same, quadratic time bound.