30
I have a series of questions in which I need feedback and answers. I will comment as to what I think, this is not a homework assignment but rather preparation for my exam.
My main problem is determining the iterations of a loop for different cases. How would go about attempting to figure that out?
Evaluate Running time.
Q2.
for(int i =0 ; i < =n ; i++) // runs n times
for(int j =1; j<= i * i; j++) // same reasoning as 1. n^2
if (j % i == 0)
for(int k = 0; k<j; k++) // runs n^2 times? <- same reasoning as above.
sum++;
Correct Answer: N × N2 × N = O(N^4)
For the following Questions below, I do not have the correct answers.
Q3. a)
int x=0; //constant
for(int i=4*n; i>=1; i--) //runs n times, disregard the constant
x=x+2*i;
My Answer: O(n)
b) Assume for simplicity that n = 3^k
int z=0;
int x=0;
for (int i=1; i<=n; i=i*3){ // runs n/3 times? how does it effect final answer?
z = z+5;
z++;
x = 2*x;
}
My Answer: O(n)
c) Assume for simplicity that n = k^2,
int y=0;
for(int j=1; j*j<=n; j++) //runs O(logn)? j <= (n)^1/2
y++; //constant
My Answer: O(logn)
d)
int b=0; //constant
for(int i=n; i>0; i--) //n times
for(int j=0; j<i; j++) // runs n+ n-1 +...+ 1. O(n^2)
b=b+5;
My Answer: O(n^3)
(e)
int y=1;
int j=0;
for(j=1; j<=2n; j=j+2) //runs n times
y=y+i;
int s=0;
for(i=1; i<=j; i++) // runs n times
s++;
My Answer: O(n)
(f)
int b=0;
for(int i=0; i<n; i++) //runs n times
for(int j=0; j<i*n; j++) //runs n^2 x n times?
b=b+5;
My Answer: O(n^4)
(g) Assume for simplicity that n