1

What is the time complexity for each of the following code segments?

1. int i, j, y=0, s=0;
for ( j = 1; j <= n; j ++) 
{
  y=y+j;
}
for ( i = 1; i <= y; i ++) 
{
  s++;
}

My answer is O(2n) since it iterates through each loop n times and there are two loops

2. function (n) {
  while (n > 1) {
  n = n/3 ;
}

My answer for this one is n^(1/3) since n becomes a third of its size every time

3. function (n) {
int i, j, k ;
for ( i = n/2; i <= n; i ++ ) {   //n/2?
  for ( j = 1; j <= n; j = 2*j ) {  //logn
    for ( k = 1; k <= n; k = 2*k ) {  //logn
      cout << ”COSC 2437.201, 301” << endl;
    }
  }
}
}

I said the answer to this one was O(log2*log2n*n/2) but I'm pretty confused about the first for loop. The loop only has to iterate half of n times, so it would be n/2 correct? Thanks for your help, everyone.

Jason
  • 25
  • 1
  • 8

1 Answers1

2

Question 1

The first loop is O(n), as it runs n times. However, the second loop executes y times, not n - so the total runtime is not "2n"

At the end of the first loop, the value of y is:

enter image description here

Therefore the second loop dominates since it is O(n^2), which is thus also the overall complexity.

Question 3

This answer is correct (but again, drop the factors of 2 in O-notation).

However, you must be careful about naively multiplying the complexities of the loops together, because the boundaries of the inner loops may depend on the spontaneous values of the outer ones.

Question 2

This is not O(n^(1/3))! Your reasoning is incorrect.

If you look closely at this loop, it is in-fact similar to the reverse of the inner loops in question 3:

  • In Q3 the value of k starts at 1 and is multiplied by 2 each time until it reaches n
  • In Q2 the value of n is divided by 3 each time until it reaches 1.

Therefore they both take O(log n) steps.

(As a side note, a O(n^(1/3)) loop would look something like this:)

for (int i = 1; i*i*i <= n; i++)
   /* ... */
meowgoesthedog
  • 14,670
  • 4
  • 27
  • 40