-2

I have the code below and am trying figure out the big O worst case running time for it. I think that the first loop is O(log N), but I am not sure what the second loop is. I thought maybe it was O(N) but that didn't seem right. Any insights would be very helpful.

    for(int jump = inList.size(); jump > 0; jump/= 2) {
        for(int i = 0; i < inList.size(); i = ++i * jump) {
Jon Doe
  • 167
  • 1
  • 11
mickeyvolmouse
  • 31
  • 2
  • You might want to check out this link https://stackoverflow.com/questions/362059/what-is-the-big-o-of-a-nested-loop-where-number-of-iterations-in-the-inner-loop – Solomon Ayoola Sep 16 '19 at 19:49
  • Sorry DIVIDE_BY_TWO is the number 2 – mickeyvolmouse Sep 16 '19 at 23:41
  • This is tricky. For large enough values of n, the inner loop will always execute only 2 times. However, for smaller values of n, you could argue it executes a coefficient of n amount of times. Id say it's O(log(n)), but there's also a case for it being O(nlog(n)) – Jon Doe Sep 17 '19 at 00:39
  • Possible duplicate of [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?](https://stackoverflow.com/questions/362059/what-is-the-big-o-of-a-nested-loop-where-number-of-iterations-in-the-inner-loop) – Dulaj Kulathunga Sep 18 '19 at 04:40

1 Answers1

1

This is going to be a O(log(n)) algorithm because the outer loop is clearly O(log(n)) and for large enough N the inner loop is going to finish executing in constant (2) iterations because n/2 * (n+1)/4 = (n^2+n)/8 > n for n > 6. For all values greater than 6 the inner for loop always iterates twice, big O deals with large cases (approaching infinity) in which case the inner loop is constant.

Jon Doe
  • 167
  • 1
  • 11