Determining the time complexity for code segments

Question

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.

Answer 1

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:

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++)
   /* ... */