Le cas le plus rapide correspond à utiliser systématiquement $y \gets y/2$.On passe de $B$ à 1 en $\log_2 B$ étapes.

L'algorithme est donc en $O(\log B)$.