Bonjour,
 
Je suis étudiant en L2 informatique et j'ai des cours sur la complexité des algorithmes, cependant même avec l'aide de ces cours j'ai du mal avec un exercice d'une de mes annales, voici l'exercice :
 
"Soit M un nombre aléatoire dont l’écriture propre en base 2 comporte n chiffres. Quelle est la complexité temporelle moyenne de l’algorithme suivant ?"
 
x := M ; i := 0 ;
Tant que (x mod 2 = 0) faire
   x := x/2 ; i := i + 1 ;
Fin tant que
 
Je sais que la réponse à cette question est que la complexité moyenne est en thêta(1). Or je ne comprends pas pourquoi elle n'est pas en thêta(log n). Peut-être que je n'ai pas bien compris l'algorithme, mais dans ma tête je prends un exemple : 16
 
16 comporte 5 chiffres en base 2 (10000), on va rentrer dans la boucle 4 fois avant d'avoir fini : 16/2, 8/2, 4/2, 2/2. Or 2^4 = 16, même raisonnement pour 32, 64, 128, etc.. Je ne dois pas avoir le bon raisonnement puisque de ce fait j'aurais dis que la complexité était en thêta(log n), quelqu'un pourrait-il m'éclairer sur cet exercice ?
 
Merci d'avance pour votre aide !

parceque log(n) est la complexité maximale
Je suis trop rouillé pour faire une démonstration propre, mais  
 
Le nombres impaire (2n+1) : 0 tour de boucle ( et ça représente moitié des nombres entier)
Les nombres paires qui sont des nombres impaires doublés ( 2 x (2n+1)) : 1 tour (ça représente  une autre grosse brouette)