Why does this nested loop have O(n) time complexity?-CodePudding

I have a test in computer sience about complexity and I have this question:

int counter = 0;
for (int i = 2; i < n;   i) {
    for (int j = 1; j < n; j = j * i) {
        counter  ;
    }
}

My solution is O(nlogn) because the first for is n-2 and the second for is doing log in base i of n and it's n-2 * logn, that is O(nlogn)-

But my teacher told us it's n and when I tried in cLion to run it it gives me 2*n and it's O(n). Can someone explain why it is O(n)?

CodePudding user response：

Empirically, you can see that this is correct (that's around the right value for the sum of the series), for n=100 and n=1,000

If you want more intuition, you can think about the fact that for nearly all the series, i > sqrt(2).

for example, if n = 100 then 90% of values have i > 10, and for n = 1,000 97% have i > 32.

From that point onwards, all iterations of the outer loop will have at most 2 iterations in the inner loop (since log(n) with base sqrt(n) is 2, by definition).

If n grows really large, you can also apply the same logic to show that from the cube root to the square root, log is between 2 and 3, etc...

CodePudding user response：

This would be O(nlogn) if j was incremented by i each iteration, not multiplied by it. As it is now, the j loop increases much more slowly than n grows, which is why your teacher and CLion state the time complexity as O(n).

CodePudding user response：

For some value of i, j will go like

1  i^1  i^2  i^3  ....

So the number of times the in loop needs to execute is found like

log_i(n)

which would lead to the following:

log_2(n)   log_3(n)   log_4(n)   ....

But... there is the stop condition j < n which need to be considered.

Now consider n as a number that can be written as m^2. As soon a i reach the value m all remaining inner loop iterations will only be done for j equal 1 and j equal i (because i^2 will be greater than n). In other words - there will only be 2 executions of the inner loop.

So the total number of iterations will be:

2 * (m^2 - m)   number_of_iteration(i=2:m)

Now divide that by n which is m^2:

(2 * (m^2 - m)   number_of_iteration(i=2:m)) / m^2

gives

2 * (1 -1/m)   number_of_iteration(i=2:m) / m^2

The first part 2 * (1 -1/m) clear goes towards 2 as m goes to inifinity.

The second part is (at worst):

 (log_2(n)   log_3(n)   log_4(n)   ...   log_m(n)) / m^2

 (log_2(n)   log_3(n)   log_4(n)   ...   log_m(n)) / n

As log(x)/x goes towards zero as x goes towards infinity, the above expression will also go towards zero.

So the full expression:

(2 * (m^2 - m)   number_of_iteration(i=2:m)) / m^2

will go towards 2 as m goes towards infinity.

In other words: The total number of iterations divided by n will go towards 2. Consequently we have O(n).

CodePudding user response：

Note that it's j=j*i, not j=j*2. That means most of the time, the inner loop will only have one pass. For example, with n of 33, the inner loop will only have one pass when i is in [7,33).

n = 33

j = 32
j = 16
j =  8 27
j =  4  9 16 25
j =  2  3  4  5  6
j =  1  1  1  1  1  1  1  1  1  1      1   1
--------------------------------------------
i =  2  3  4  5  6  7  8  9 10 11 ... 28  29

If you think of the above as a graph, it looks like the complexity of algorithm is O( area under 1/log(n) ). I have no idea how to prove that, and calculating that integral involves the unfamiliar-to-me logarithmic integral function. But the Wikipedia page does say this function is O( n / log n ).

Let's do it experimentally.

#include <stdio.h>

int main( void ) {
   for ( int n = 20; n <= 20000;   n ) {
      int counter = 0;
      for ( int i = 2; i < n;   i ) {
         for ( int j = 1; j < n ; j *= i ) {
              counter;
         }
      }

      if ( n % 1000 == 0 )
         printf( "%d: %.3f\n", n, counter / (n-1) );
   }
}

1000: 2.047
2000: 2.033
3000: 2.027
4000: 2.023
5000: 2.021
6000: 2.019
7000: 2.017
8000: 2.016
9000: 2.015
10000: 2.014
11000: 2.013
12000: 2.013
13000: 2.012
14000: 2.012
15000: 2.011
16000: 2.011
17000: 2.011
18000: 2.010
19000: 2.010
20000: 2.010

So it doubles plus a little. But the extra little shrinks as n grows. So it's definitely not O( n log n ). It's something of the form O( n / f(n) ), where f() produces some number ≥1. It looks like it could be O( n / log n ), but that's pure speculation.

Whatever f(n) is, O( n / f(n) ) approaches O( n ) as n approaches infinity. So we can also call this O( n ).