Determining the big-O runtimes of these different loops?

Question

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 = 3k, for some positive integer k.

   int x=0;
   for(int i=1; i<=n; i=i*3){  //runs 1, 3, 9, 27...for values of i. 
     if(i%2 != 0) //will always be true for values above
      for(int j=0; j<i; j++) // runs n times
        x++;
    }

My Answer: O (n x log base 3 n? )

(h) Assume for simplicity that n = k2, for some positive integer k.

   int t=0;
   for(int i=1; i<=n; i++) //runs n times
      for(int j=0; j*j<4*n; j++) //runs O(logn)
         for(int k=1; k*k<=9*n; k++) //runs O(logn)
            t++;

My Answer: n x logn x log n = O(n log n^2)

(i) Assume for simplicity that n = 2s, for some positive integer s.

   int a = 0;
   int k = n*n;
     while(k > 1) //runs n^2
     {
       for (int j=0; j<n*n; j++) //runs n^2
          { a++; }
        k = k/2;
    }

My Answer: O(n^4)

(j)

  int i=0, j=0, y=0, s=0;
  for(j=0; j<n+1; j++) //runs n times
     y=y+j; //y equals n(n+1)/2 ~ O(n^2)
  for(i=1; i<=y; i++) // runs n^2 times
     s++;

My Answer: O(n^3)

(k) int i=1, z=0; while( z < n*(n+1)/2 ){ //arithmetic series, runs n times z+=i; i++; }

My Answer: O(n)

(m) Assume for simplicity that n = 2s, for some positive integer s.

  int a = 0;
  int k = n*n*n;
  while(k > 1) //runs O(logn) complexity
   {
     for (int j=0; j<k; j++) //runs n^3 times
      { a--; }
     k = k/2; 
    }

My Answer: O(n^3 log n)

Question 4

• a) True - since its bounded below by n^2
• b) False - f(n) not strictly smaller than g(n)
• c) True
• d) True -bounded by n^10
• e) False - f(n) not strictly smaller than g(n)
• f) True
• g) True
• h) false - since does not equal O(nlogn)
• i) true
• j) not sure
• k) not sure
• l) not sure - how should i even attempt these?*

Thanks in advance.

Solution

Let's go through these one at a time.

Part (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)

Yep! That's correct. The loop runs O(n) times and does O(1) work per iteration.

Part (b)

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)

Not quite. Think about the values of i as the loop progresses. It will take on the series of values 1, 3, 9, 27, 81, 243, ..., 3^k. Since i is tripling on each iteration, it takes on successive powers of three.

The loop clearly only does O(1) work per iteration, so the main question here is how many total iterations there will be. The loop will stop when i > n. If we let k be some arbitrary iteration of the loop, the value of i on iteration k will be 3^k. The loop stops when 3^k > n, which happens when k > log₃ n. Therefore, the number of iterations is only O(log n), so the total complexity is O(log n).

Part (c)

int y=0; 
for(int j=1; j*j<=n; j++) //runs O(logn)?  j <= (n)^1/2
    y++; //constant

My Answer: O(logn)

Not quite. Notice that j is still growing linearly, but the loop runs as long as j² ≤ n. This means that as soon as j exceeds √ n, the loop will stop. Therefore, there will only be O(√n) iterations of the loop, and since each one does O(1) work, the total work done is O(√n).

Part (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)

Not quite. You're actually doubly-counting a lot of the work you need to do. You're correct that the inner loop will run n + (n-1) + (n-2) + ... + 1 times, which is O(n²) times, but you're already summing up across all iterations of the outer loop. You don't need to multiply that value by O(n) one more time. The most accurate answer would be O(n²).

Part (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)

Yep! Exactly right.

Part (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)

Again, I believe you're overcounting. The inner loop will run 0 + n + 2n + 3n + 4n + ... + n(n-1) = n(0 + 1 + 2 + ... + n - 1) times, so the total work done is O(n³). You shouldn't multiply by the number of times the outer loop runs because you're already summing up across all iterations. The most accurate runtime would be O(n³).

Part (g)

int x=0;
for(int i=1; i<=n; i=i*3){  //runs 1, 3, 9, 27...for values of i. 
   if(i%2 != 0) //will always be true for values above
      for(int j=0; j<i; j++) // runs n times
         x++;
 }

My Answer: O (n x log base 3 n? )

The outer loop here will indeed run O(log n) times, but let's see how much work the inner loop does. You're correct that the if statement always evaluates to true. This means that the inner loop will do 1 + 3 + 9 + 27 + ... + 3^{log₃ n} work. This summation, however, works out to (3^{log₃ n + 1} - 1) / 2 = (3n + 1) / 2. Therefore, the total work done here is just O(n).

Part (h)

int t=0;
for(int i=1; i<=n; i++) //runs n times
   for(int j=0; j*j<4*n; j++) //runs O(logn)
      for(int k=1; k*k<=9*n; k++) //runs O(logn)
         t++;

My Answer: n x logn x log n = O(n log n^2)

Not quite. Look at the second loop. This actually runs O(√n) times using the same logic as one of the earlier parts. That third inner loop also runs O(√n) times, and so the total work done will be O(n²).

Part (i)

int a = 0;
int k = n*n;
while(k > 1) //runs n^2
{
    for (int j=0; j<n*n; j++) //runs n^2
       { a++; }
     k = k/2;
}

My Answer: O(n^4)

Not quite. The outer loop starts with k initialized to n², but notice that k is halved on each iteration. This means that the number of iterations of the outer loop will be log (n²) = 2 log n = O(log n), so the outer loop runs only O(log n) times. That inner loop does do O(n²) work, so the total runtime is O(n² log n).

Part (j)

int i=0, j=0, y=0, s=0;
for(j=0; j<n+1; j++) //runs n times
   y=y+j; //y equals n(n+1)/2 ~ O(n^2)
for(i=1; i<=y; i++) // runs n^2 times
   s++;

My Answer: O(n^3)

Close, but not quite! The first loop runs in time O(n) and by the time it's done, the value of j is Θ(n²). This means that the second loop runs for time Θ(n²), so the total time spent is Θ(n²).

Part (k)

 int i=1, z=0;
 while( z < n*(n+1)/2 )//arithmetic series, runs n times
 {
       z+=i; i++;
 }

My Answer: O(n)

That's correct!

Part (l)

That's odd, there is no part (l).

Part (m)

int a = 0;
int k = n*n*n;
while(k > 1) //runs O(logn) complexity
{
   for (int j=0; j<k; j++) //runs n^3 times
   { a--; }
   k = k/2; 
}

My Answer: O(n^3 log n)

Close, but not quite. You're right that the outer loop runs O(log n) times and that the inner loop does O(n³) work on the first iteration. However, look at the number of iterations of the inner loop more closely:

n³ + n³ / 2+ n³ / 4 + n³ / 8 + ...

= n³ (1 + 1/2 + 1/4 + 1/8 + ...)

≤ 2n³

So the total work done here is actually only O(n³), even though there are log n iterations.

Question 4

Your answers are all correct except for these:

f) True

This is actually false. The expression on the left is

(3/2)n^3/2 + 5n² + lg n

which is not Ω(n² √n) = Ω(n^5/2)

For (j), note that log n⁶ = 6 log n. Does that help?

For (k), ask whether both sides are O and Ω of one another. What do you find?

For (l), use the fact that a^{log_b c} = c^log_ba. Does that help?

Hope this helps!