The "too much time has passed" bound on each iteration guarantees that you don't end up running an iteration forever, and makes the algorithm O(2^N), since the

The "too much time has passed" bound on each iteration guarantees that you don't end up running an iteration forever, and makes the algorithm O(2^N), since the number of programs up to N bits long is 2^(N+1) - 1.