Cet algorithme semble polynomial. En fait, ce n'est pas du tout le cas.

La complexité d'une algorithme n'est pas simplement le nombre d'opérations que celui-ci exécute. C'est la fonction qui relie ce nombre d'opérations à la taille (de l'instance) du problème (des données).

Ici, la taille des données est le nombre de chiffres que l'on utilise pour noter $x$ & $y$, c'est à dire $\log x + \log y$ (la base du $\log$ est la base dans laquelle on compte).
Si on note $n_y$ le nombre de chiffres de $y$, on voit que cet algorithme est en $O(2^{n_y})$, cet algorithme est donc exponentiel.