Complexité pour les boucles nestedes divisées par 2

J’essaie de comprendre la complexité d’une boucle for en utilisant la notation Big O. Je l’ai déjà fait dans mes autres classes, mais celle-ci est plus rigoureuse que les autres car elle est basée sur l’algorithme actuel. Le code est comme suit:

for(i=n ; i>1 ; i/=2) //for any size n { for(j = 1; j < i; j++) { x+=a } } 

Je suis arrivé que la première boucle est de O (log_2 (n)). Quant à la deuxième boucle, je suis un peu perdu! Merci pour l’aide dans l’parsing.

Pour résoudre formellement la complexité temporelle de votre algorithme, vous pouvez utiliser les étapes suivantes avec la notation Sigma:

entrez la description de l'image ici

Jetez également un coup d’œil à la dernière diapositive de ce document très intéressant rédigé par M. Jauhar.

Le nombre total d’itérations de la boucle interne est n + n / 2 + n / 4 + … + 1, ce qui correspond à environ 2n. Donc, la complexité est O (n).

La complexité devrait être O(n) . Il forme une série géomésortingque (pas exactement mais approximativement).

La boucle court pour n+ n/2 + n/4 + .... +1 ce qui correspond à environ 2n .

Et O(2n) = O(n) .