Code Number of Iterations of Growth Function Order 0 for(int i=0;i<n;i++){ S1;}
ID: 3880886 • Letter: C
Question
Code
Number of Iterations of
Growth Function
Order
0
for(int i=0;i<n;i++){
S1;}
1+(n+1)+n +n
1
for(int i=1;i<n;i++){
S2;}
2
for(int i=0;i<=n;i++){
S3;}
3
for(int i=5;i<=n;i++){
S4;}
4
for(int i=8;i<n;i++){
S5;}
5
for(int i=0;i<n;i=i+2){
S6;}
6
for(int i=0;i<n;i=i+5){
S7;}
7
for(int i=n;i>1;i=i/3){
S8;}
8
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
S9;
}
9
for(int i=0;i<n;i++){
for(int j=0;j<=n;j++){
S10;
}
Code
Number of Iterations of
Growth Function
Order
0
for(int i=0;i<n;i++){
S1;}
n1+(n+1)+n +n
O(n)1
for(int i=1;i<n;i++){
S2;}
2
for(int i=0;i<=n;i++){
S3;}
3
for(int i=5;i<=n;i++){
S4;}
4
for(int i=8;i<n;i++){
S5;}
5
for(int i=0;i<n;i=i+2){
S6;}
6
for(int i=0;i<n;i=i+5){
S7;}
7
for(int i=n;i>1;i=i/3){
S8;}
8
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
S9;
}
9
for(int i=0;i<n;i++){
for(int j=0;j<=n;j++){
S10;
}
Explanation / Answer
0:
for(i=0;i<n;i++){
S1;
}
It is clear that there are 1 asignation, n comparations, and n incrementations.
Growth function=t0 + t1*n + t2*n = t0 + (t1+t2)n = c0+c1*n
BigO=O(n)
1:
for(i=1;i<n;i++){
S2;
}
It is clear that there are 1 asignation, n comparations, and n incrementations.
Growth function=t0 + t1*(n-1) + t2*(n-1) = t0 + (t1+t2)(n-1) = c0+c1*(n-1)
BigO=O(n)
2:
for(i=0;i<=n;i++){
S3;
}
It is clear that there are 1 asignation, n comparations, and n incrementations.
Growth function=t0 + t1*(n+1) + t2*(n+1) = t0 + (t1+t2)(n+1) = c0+c1*(n+1)
BigO=O(n)
3:
for(i=5;i<=n;i++){
S4;
}
It is clear that there are 1 asignation, n comparations, and n incrementations.
Growth function=t0 + t1*(n+1) + t2*(n+1)-5 = t0 + (t1+t2)(n+1)-5 = c0+c1*(n+1)
BigO=O(n)
4:
for(i=8;i<n;i++){
S5;
}
It is clear that there are 1 asignation, n comparations, and n incrementations.
Growth function=t0-8 + t1*(n) + t2*(n) = t0-8 + (t1+t2)(n) = c0+c1*(n)
BigO=O(n)
5:
for(i=0;i<n;i=i+2){
S6;
}
It is clear that there are 1 asignation, n/2 comparations, and n/2 incrementations.
Growth function=t0 + t1*(n/2) + t2*(n/2) = t0 + (t1+t2)(n/2) = c0+c1*(n/2)
BigO=O(n)
6:
for(i=0;i<n;i=i+5){
S7;
}
It is clear that there are 1 asignation, n/5 comparations, and n/5 incrementations.
Growth function=t0 + t1*(n/5) + t2*(n/5) = t0 + (t1+t2)(n/5) = c0+c1*(n/5)
BigO=O(n)
7:
for(i=n;i>1;i=i/3){
S8;
}
It is clear that there are 1 asignation, n/3 comparations, and n/3 incrementations.
Growth function=t0 + t1*(n/3) + t2*(n/3) = t0 + (t1+t2)(n/3) = c0+c1*(n/3)
BigO=O(n)
8:
for(i=0;i<n;i++){
for(j=0;j<n;j++){
S9;
}
}
It is clear that there are 2 asignation, n^2 comparations, and n^2 incrementations.
Growth function=t0+2 + t1*(n^2) + t2*(n^2) = t0+2 + (t1+t2)(n^2) = c0+c1*(n^2)
BigO=O(n^2)
9:
for(i=0;i<n;i++){
for(j=0;j<=n;j++){
S10;
}
}
It is clear that there are 2 asignation, n^2 comparations, and n^2 incrementations.
Growth function=t0+2 + t1*(n^2+1) + t2*(n^2+1) = t0+2 + (t1+t2)(n^2+1) = c0+c1*(n^2+1)
BigO=O(n^2)