Big-O of while loop nested inside for loop is O(n), why?

user_15066328 0
Viewed 118

I am trying to figure out why the following is O(n). My doubt is actually on how to figure out the number of iterations of the inner loop without substituting the values.

*Edit: In other words, can anyone show me the derivation using sigma notation?

n = 10
j = 1
for i in range(n):
      while j < i:
        j *= 2

It is easy to see that the inner while will be executed at most one time per i value, but I am struggling to see more generally how to figure out the last value for j in order to perform the corresponding manipulations in the sums using T(n). Can anyone show the calculation?

big-o time-complexity algorithm
2 Answers
n = 10
j = 1
for i in range(n):
      while j < i:
        j *= 2

Iteration 1: i = 1 and 1 < 1 is false;

Iteration 2: i = 2 and 1 < 2 is true, => j becomes 1 * 2 = 2; (i = 2 and j = 2);

Iteration 3: i = 3 and 2 < 3 is true, => j becomes 2 * 2 = 4; (i = 3 and j = 4);

Iteration 4: i = 4 and 4 < 4 is false; (i = 4 and j = 4);

Iteration 5: i = 5 and 4 < 5 is true, => j becomes 2 * 4 = 8; (i = 5 and j = 8);

. . .

then j = 8 will NOT be less than i for the next three iterations..

then j will be less than 9 and so on.

So, there are iterations where j < i evaluates to true, but even in those cases, that nested while loop doesn't live long.

It is a bit amortized, but overall, while j < i is still a very much lower order term.

Therefore, according to the asymptotic measurement, higher order is O(n).

user_15535370

I think I figured out a more abstract way of analyzing it which complements the previous answer and comments.

Notice that:

  1. The variable j of the while loop is defined outside of the for loop, which implies that if j < i is satisfied, j will be updated and after that, a new iteration of the for loop happens, updating i.

  2. Since j is not reset to 1 at each iteration of the for loop, we expect that the number of runs of the be O(n) < Log_2(n), which suggests that it is O(1).

  3. By inspection (as in the previous answer) we can confirm (2.), where for each i the while loop will run at most one time.

Comment:
I am a newbie on this and I was looking for a more closed mathematical proof using sigma notation in a similar fashion as in other cases with nested loops, where the total number of runs of the inner loops can be found as sums of elements of arithmetic or geometric progressions for instance, depending of the case. But the using arguments (1.) and (2.) was the closer I could get.

Anyways, many thanks for the help :)

user_150663280
Related