Le cas le plus rapide correspond à utiliser systématiquement y←y/2y←y/2.On passe de BB à 1 en log2Blog2B étapes.
L'algorithme est donc en O(logB)O(logB).