Time complexity with log in a loop

Question

What is the complexity of a loop which goes the following?

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?

"According to me" Always found this phrase amusing. We typically use "according to" to announce a third-party authority we used to arrive at a conclusion. You can't use yourself as a third-party authority. — Lightness Races in Orbit
– Lightness Races in Orbit, Commented Aug 9, 2016 at 11:46

karastojko · Accepted Answer · 2016-08-09 12:48:47Z

8

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

answered Aug 9, 2016 at 12:48

karastojko

1,1819 silver badges14 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Nick Zuber Over a year ago

Nice qualitative analysis -- \sum_{i=1}^{n} log(i) => log(n!) which allows us to use Stirling's approximation good catch!

TemplateRex · Accepted Answer · 2016-08-09 11:54:24Z

8

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

edited Aug 9, 2016 at 11:54

answered Aug 9, 2016 at 11:30

TemplateRex

71k21 gold badges176 silver badges316 bronze badges

3 Comments

Peter Over a year ago

Multiply that by the complexity of "do something".

Lightness Races in Orbit Over a year ago

How can the complexity be worse than that of a basic two-dimensional loop over n^2? How can it be worse than n*log n for that matter? Honestly asking - it's been a while since I've studied this formally. But "between quadratic and cubic" for this intuitively seems wrong to me?

TemplateRex Over a year ago

@LightnessRacesinOrbit duh, you are right, I messed up, fixed now.

Peter Mortensen · Accepted Answer · 2023-07-21 08:33:19Z

0

Let’s start with log(1)+log(2)+log(3)+...+log(n).

Roughly half of the elements of this sum are greater than or equal to log(n/2) = log(n) - log(2). Hence the lower bound of this sum is n / 2 * (log(n) - log(2)) = Omega(nlog(n)). To get the upper bound, simply multiply n by the largest element which is log(n), hence O(nlog(n)).

edited Jul 21, 2023 at 8:33

Peter Mortensen

31.4k22 gold badges110 silver badges134 bronze badges

answered Aug 9, 2016 at 15:38

piotrekg2

1,27713 silver badges21 bronze badges

Collectives™ on Stack Overflow

Time complexity with log in a loop

3 Answers 3

1 Comment

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related