Time complexity with log in loop

Question

what is the complexity of a loop which goes this

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < log(i); j++)
    {
        // do something
    }
}

According to me the inner loop will be running log(1)+log(2)+log(3)+...+log(n) times so how do i calculate its complexity?

Answer 1

So, you have a sum log(1) + log(2) + log(3) + ... + log(n) = log(n!). By using Stirling's approximation and the fact that ln(x) = log(x) / log(e) one can get

log(n!) = log(e) * ln(n!) = log(e) (n ln(n) - n + O(ln(n)))

which gives the same complexity O(n ln(n)) as in the other answer (with slightly better understanding of the constants involved).

Answer 2

Without doing this in a formal manner, such complexity calculations can be "guessed" using integrals. The integrand is the complexity of do_something, which is assumed to be O(1), and combined with the interval of log N, this then becomes log N for the inner loop. Combined with the outer loop, the overall complexity is O(N log N). So between linear and quadratic.

Note: this assumes that "do something" is O(1) (in terms of N, it could be of a very high constant of course).