posted 5 years ago

Although I know that the Big O of the following code is O(n) I'm a bit lost as to why... any help towards understand would be much appreciated! At first glance to me it looks like the outer loop would be O(log n) and the inner loop looks like O(n). My guess is the catch is somewhere in the condition check for the inner loop.

posted 5 years ago

- 2

The outer loop is O(logn) and the inner loop is O(n). The combined loop is O(nlogn), and since for sufficiently large n, the logn is insignificant relative to n, you get O(n). As a general rule, given multiple orders of growth the only one that 'matters' is the fastest growing order. In this case it is the inner loop, which O(n).

Steve

Mike Simmons

Ranch Hand

Posts: 3090

14

posted 5 years ago

- 2

I disagree a bit there - O(n*log(n)) would not, generally, be viewed as equivalent to O(n). No matter how big n is. The thing is, this algorithm isn't O(n*log(n)) at all - despite appearances.

The key is that while there are log(n) iterations of the outer loop, those outer loops aren't all equal. The first one executes the inner loop n times, and the next one n/3 times. The total number of executions of the inner loop is given by the series:

n + n/3 + n/3^2 + n/3^3 + n/3^4 ...

This is a geometric series that converges to n / (1 - 1/3) or 1.5 n - which is O(n).

(Yeah, it's not an infinite series in practice - but since in practice it's something

The key is that while there are log(n) iterations of the outer loop, those outer loops aren't all equal. The first one executes the inner loop n times, and the next one n/3 times. The total number of executions of the inner loop is given by the series:

n + n/3 + n/3^2 + n/3^3 + n/3^4 ...

This is a geometric series that converges to n / (1 - 1/3) or 1.5 n - which is O(n).

(Yeah, it's not an infinite series in practice - but since in practice it's something

*less*than that series, 1.5n serves as a close upper bound.)
posted 5 years ago

So I should look at it as N * the geometric series of (1/3)^i from i=0 to infinity which can be summed up as (1 / (1-x)). x in this case would be 1/3 which is between 0 and 1 (a requirement for geometric series I think) so then I end up with N * (1 / (1-(1/3)) which simplifies to N*(3/2) which is just O(n)? I had to brush up on my geometric series stuff, but I think I got it now. Thanks!

Mike Simmons

Ranch Hand

Posts: 3090

14

posted 5 years ago

Yes, that's right. I had to double-check the formula for the sum of a geometric series myself. Often big-O determination requires very little math, just deciding how many layers of a loop there are. Or recognizing a log n progression, as you did here. But the geometric series is one of the more common series that shows up now and then; it's nice to at least know that there

Perry Campbell wrote:So I should look at it as N * the geometric series of (1/3)^i from i=0 to infinity which can be summed up as (1 / (1-x)). x in this case would be 1/3 which is between 0 and 1 (a requirement for geometric series I think) so then I end up with N * (1 / (1-(1/3)) which simplifies to N*(3/2) which is just O(n)? I had to brush up on my geometric series stuff, but I think I got it now. Thanks!

Yes, that's right. I had to double-check the formula for the sum of a geometric series myself. Often big-O determination requires very little math, just deciding how many layers of a loop there are. Or recognizing a log n progression, as you did here. But the geometric series is one of the more common series that shows up now and then; it's nice to at least know that there

*is*a formula for it, and look it up when you need it.