aspose file tools*
The moose likes Java in General and the fly likes Big O Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Big O" Watch "Big O" New topic
Author

Big O

Perry Campbell
Greenhorn

Joined: May 22, 2012
Posts: 6

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.

Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4181
    
  21

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
Perry Campbell
Greenhorn

Joined: May 22, 2012
Posts: 6

Thanks for the explanation. That makes sense. Reminds me of limits in calculus =).
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
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.)
Perry Campbell
Greenhorn

Joined: May 22, 2012
Posts: 6

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: 3018
    
  10
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.
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Big O