Can someone help me with calculating the time complexity of the inner loop? As far as I understand, the outer one will be O(n). But I have no idea how to calculate what happens inside the second one.

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

CodePudding user response：

For every iteration of "outer loop", inner loop runs n/i times

So, total complexity of this will be given by:

n/2   n/3   n/4   ...
= n * (1/2   1/3   1/4 ...)

For the right term above, upper bound is ln(n)

Hence, complexity of this code is O(n log n).

CodePudding user response：

The inner loop runs from 2 up to but not including n/i times. You can express it as n/i - 2.

If we run the inner loop n - 2 times (since that's the number of times the outer loop runs), we get the following summation:

(n/2 - 2)   (n/3 - 2)   ...   (3 - 2)

I have a hunch but can't remember 100% that this series sums up to log_e(n) * n or similar. So in terms of time complexity, this becomes O(log n * n).

CodePudding user response：

The loop exits as soon as i * j ≥ n, i.e. when j = ceiling(n / i) ~ n / i. As it starts from j=2, the number of iterations is ceiling(n / i) - 1.