Quelle est la durée de ce pseudo-code

Question

i = 1; 
while (i <= n) 
    j = i; 
    x = x+A[i]; 
    while (j > 0) 
    y = x/(2*j); 
    j = j/2; // Assume here that this returns the floor of the quotient 
    i = 2*i; 
return y; 

Je ne suis pas sûr de ma réponse, je me suis O (n).

Answer 1

Permet de supprimer x et y variables car cela n'affecte pas la complexité.

i = 1; 
while (i <= n) 
    j = i;  
    while (j > 0) 
     j = j/2; 
    i = 2*i; 

1. Dans la boucle intérieure vous chaque division de temps j par 2, donc en fait il est doublure est pas O(logn). Par exemple quand j est 16 vous ferez 5 étapes (O(log16)+1): 8,4,2,1,0.
2. Dans la boucle externe, vous multipliez chaque fois i par 2, donc il est également O(logn).

Donc la complexité globale sera O(logn * logn).