Big-O notation for complex loop-CodePudding

I can not guess the Big-O notation for this loops.

for (int j = 2; j < N; j  ) {
    for (int k = 2*j; k <= N; k  = j) {
        nums[k] = false;
    }
}

How to calculate the algorithm complexity for this loop?

CodePudding user response：

The trick for this is Calculus to replace a sum by an integral that we understand.

for y from 2 to N:
    do roughly N/j things

So we have a sum of:

N/2   N/3   N/4   ...   N/N
    = N (1/2   1/3   1/4   ...   1/N)

And that sum can be approximated with the integral from 1 to N of 1/x. Whose integral is log(x). So, modulo errors, it requires O(N log(N)) steps.

I waved my hands vigorously. But I assure you that the rigorous details can be filled in, and "replace sum by approximate integral" has a O(1) error.

CodePudding user response：

for (int j = 2; j < N; j  ) {  ==> it runs for "N-2" times
  for (int k = 2*j; k <= N; k  = j) {
      nums[k] = false;
  }
}

for inner loop, let 'h' be no. of times inner loop has been called

   if j = 2 ==> values of k are 4,6,8,12,.....,2h ==> 2(2),3(2),....,h(2)
      j = 3 ==> values of k are 6,9,12,15,.....,3h ==> 3(2),3(3),....,h(3)
      :
      :
      j = N-1 ==> values of k are 2(N-1),3(N-1),4(N-1).......h(N-1)
 
here, inner loop stops when value of k > N

      => last time loop called will be for k < N or k = N
      => h(N-1) = N
      => h = N/N-1 => no of times inner loop is called

T(N) = (N-2) * (N/N-1) = O(N^2);