'Time complexity of the inner loop

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++) {
}
algorithmtime-complexitycomputer-science


Solution 1:[1]

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).

Solution 2:[2]

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.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1
Solution 2 Yves Daoust

Related Questions