Avant tout : attention ceci est AVANCÉ et HORS PROGRAMME (c'est de la "Note" de la correction dont il s'agit ; voire la footnote (1) correspondante)
Vous y êtes presque dans votre raisonnement. Le seul point (peut être pas dit assez clairement) c'est que c'est la plus grande valeur, c.-à-d. x^n que l'on veut représenter exactement.
Et donc, oui s est en O(log(m)) ; mais simplement m est ici x^n : d'où n * log(x) (qui est le log de x^n)