lambda1@tg says to YSITD
Actually, there are subtle issues here. We are trying to deal with the worst input possible. It is possible that you discard more than half the choices for any given steps, but this argument does not account for the worst input