below_avg_st below_avg_st - 3 years ago 86
C Question

Big O of nested loop that with varying iterations?

I'm having a bit of trouble figuring out the Big O run time for the two set of code samples where the iterations depend on outside loops. I have a basic understanding of the Big O run times and I can figure out the run times for simpler code samples. I'm not too sure how some lines are affecting the run time.

I would consider this first one O(n^2). However, I'm not certain.

for(i = 1; i < n; i++){
for(j = 1000/i; j > 0; j--){ <--Not sure if this is still O(n)
arr[j]++; /* THIS LINE */
}
}


I'm a bit more lost with this one. O(n^3) possibly O(n^2)?

for(i = 0; i < n; i++){
for(j = i; j < n; j++){
while( j<n ){
arr[i] += arr[j]; /* THIS LINE */
j++;
}
}
}


I found this post and I applied this to the first code sample but I'm still unsure about the second. What is the Big-O of a nested loop, where number of iterations in the inner loop is determined by the current iteration of the outer loop?

Answer Source

For the second loop (which it appears that you still need an answer for), you have sort of a misleading bit of code, where you have 3 nested loops, so at first glance, it makes sense that the runtime is O(n^3).

However, this is incorrect. This is because the innermost while loop modifies j, the same variable that the for loop modifies. This code is actually equivalent to this bit of code below:

for(i = 0; i < n; i++){
  for(j = i; j < n; j++){
    arr[i] += arr[j]; /* THIS LINE */
    j++;
  }
}

This is because the while loop on the inside will run, incrementing j until j == n, then it breaks out. At that point, the inner for loop will increment j again and compare it to n, where it will find that j >= n, and exit. You should be familiar with this case already, and recognize it as O(n^2).

Just a note, the second bit of code is not safe (technically), as j may overflow when you increment it an additional time after the while loop finishes running. This would cause the for loop to run forever. However, this will only occur when n = int_max().

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download