void ABC( int n ){
for( int i=1; i<= n; i++) {
for (int j=1; j<=2^n;j=j*2) {
printf(“%d”,j);
}
}
}
Step#Step 1Step 2Step 3Costc1c2c3Freq.n+1∑i=1n(n+1)∑i=1nnTot.costc1⋅(n+1)c2⋅n⋅(n+1)c3⋅n2
(The step 2 execute log2(2n)=n times and once more for checking exit conditions for every i) .
So total amount of steps is T(n)=c1⋅(n+1)+c2⋅n⋅(n+1)+c3⋅n2=(c2+c3)⋅n2+(c1+c2)⋅n+c1=O(n2)
void Example2 (int n){
int a = 0;
for (int i = 0; i < N; i++) {
for (int j = N; j > i; j--) {
a = a + i + j;
}
}
}
Step#Step 1Step 2Step 3Step 4Costc1c2c3c4Freq.1n+1∑i=1n(n−i+1)∑i=1n(n−i)Tot.costc1c2⋅(n+1)c3⋅(n+1)⋅(n+2)/2c4⋅n⋅(n+1)/2
So total amount of steps is T(n)=c1+c2⋅n+c3⋅(n+1)⋅(n+2)/2+c4⋅n⋅(n+1)/2=2c3+c4⋅n2+(c2+23c3+2c4)⋅n+(c1+c3+2c4)=O(n2)
Comments