On ne peut passer au maximum qu'une fois sur deux par $y\gets y-1$, donc on passe au moins une fois sur deux par $y \gets y/2$.

Dans le cas le pire, l'algorithme est donc aussi en $O(\log B)$.