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.

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

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 less than that series, 1.5n serves as a close upper bound.)

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

Joined: Mar 05, 2008
Posts: 3020

10

posted

0

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.