Big O of nested loop that with varying iterations?

Question

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?

score 6 · Answer 1 · answered Jul 26 '17 at 02:18

Regarding the first one. It is not O(n^2)!!! For the sake of simplicity and readability, let's rewrite it in the form of pseudocode:

for i in [1, 2, ... n]:                              # outer loop
    for j in [1, 2, ... 1000/i]:                     # inner loop
        do domething with time complexity O(1).      # constant-time operation

Now, the number of constant-time operations within the inner loop (which depends on parameter i of the outer loop) can be expressed as:

Now, we can calculate the number of constant-time operations overall:

Here, N(n) is a harmonic number (see wikipedia), and there is a very interesting property of these numbers:

Where C is Euler–Mascheroni constant. Therefore, the complexity of the first algorithm is:

Regarding the second one. It seems like either the code contains a mistake, or it is a trick test question. The code resolves to

for (i = 1; i < n; i++)
    for(j = i; j < n; j++){
        arr[j]++;
        j++;
    }

The inner loop takes

operations, so we can calculate overall complexity:

This should be the accepted answer as it corrects OP's wrong answer for question 1. — meowgoesthedog, Jul 26 '17 at 09:38

score 2 · Accepted Answer · answered Jul 26 '17 at 01:50

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

Big O of nested loop that with varying iterations?

2 Answers2