Déterminer (en fonction de n à O( ) près) le
temps de calcul de chaque boucle :
(P() est une procédure dont le temps de calcul est
constant ;
et deux(i) calcule la i-ème puissance de 2
en temps constant.)
pour i allant de 1 a n par pas de 1 faire P() finpour;Réponse O(n)
pour i allant de 1 a n par pas de 1 faireRéponse O(n2)
pour j allant de 1 a i par pas de 1 faire P() finpour;
finpour;
i:=1;Réponse O(log(n))
tant que i<n faire i:=i*2
fintantque;
pour i allant de 1 a n par pas de 1 faireRéponse O(nlog(n))
j:=1;
tant que j<n faire j:=j*2
fintantque
finpour;
i:=1;Réponse O(n)
tant que i<n faire
i:=i*2;
pour j allant de 1 a i par pas de 1 faire P() finpour;
fintantque;
i:=1;Réponse O(2n)
pour j allant de 1 a n par pas de 1 faire i:=i*2 finpour;
pour j allant de 1 a i par pas de 1 faire P() finpour;
i:=1;Réponse O(n2n)
pour k allant de 1 a n par pas de 1 faire
i:=i*2;
pour l allant de 1 a i par pas de 1 faire
pour m allant de 1 a k faire P() finpour
finpour
finpour;
pour k allant de 1 a n par pas de 1 faireRéponse O(2n)
i:=1;
pour j allant de 1 a k par pas de 1 faire i:=i*2 finpour;
pour j allant de 1 a i par pas de 1 faire P() finpour
finpour;
i:=2;Réponse O(loglog(n))
tant que i<n faire i:=i*i
fintantque;
i:=1;Réponse O(log*(n))
tant que i<n faire i:=deux(i)
fintantque;