Ermitteln der BIg O-Notation dieser Schleife

Question

for(i=0;i<n;i+=2) { 
    for(j=1;j<=n;j*=2) { 
     printf(“%d,%d\n”,i,j); 
    } 
} 

Was wäre die große O-Notation dieser Schleife?

Answer 1

Die äußere Schleife wird n/2 Iterationen tun, und jede innere Schleife wird lg_2(n) Iterationen tun. Die Gesamtlaufzeit sollte O(n*lgn) sein (hier verwende ich lg, um Log-Base 2 darzustellen).