Hi everybody! I'm new to these boards and am hoping somebody could help me out. In my Data Structures and Algorithm Analysis course we're studying Big Oh analysis and it's proving to be pretty confusing.

Here's the code fragment I'm analyzing.



Braces were excluded to save space.
I've been trying to figure out what type of algorithm this falls under. I first started with the inner most loop, figuring out how many times it executes for each value of i, as well as the total for each value of n. What I noticed is that for values of n, n^3 isn't that far off from the total. Is that just a coincidence and I'm looking at this the wrong way? I thought if the innermost is executing roughly n^3 times then it might be O(N^3). If anybody could help me out I would be so thankful.

KYA has a nice Big O notation tutorial.
http://www.dreamincode.net/forums/showtopic125427.htm

Taking this a piece at a time:

Outer Loop: O(n)
First Inner Loop: it goes from 1 to i^2, at i's largest value this is n^2: O(n^2)

So far we have O(n^3) not counting anything else

Conditional check is constant: O(1)

Most inner loop: 0 - largest value of j which is n^2. The key point is that this loop isn't executed every iteration, only when the remainder of j divided by i is 0 (i.e. they are the same or i is a multiple of j). Knowing that, it'll get called at least once for each iteration of the outer most loop.

So if we did a rough (I emphasize rough) estimate we'd have O(n^2) * O(n^2) * O(n) = O(n^5) if and only if there was no conditional for the inner most loop

I'd say O(n^3) though.

Big-O is a worst-case complexity, so never cut any operations off while calculating it. It's definitely not O(n^3), let me check if it's O(n^5)...

Edit: Bah, stupid me, I was playing around with the infinite series to solve this simple little thing. I need to get more sleep and some coffee... The if-statement will be true i times. Because out of i^2 numbers, only i of them are divisible by i itself. So the second loop can be treated as O(n) because that's how many times it will be fully executed. So the whole thing is O(n^4)

This post has been edited by Neumann: 14 Sep, 2009 - 10:56 AM

Neumann, that logic sounds a lot simpler than mine. lol.
I ended up looking at the summation of n, 2n, 3n, ... , nn (from the amount of times j is executing), factored out the n and had 1/2(n(n(n+1), which is 1/2(n^3 + n^2). From here I was still convinced on O(n^3) but by furthering that as the summation of 1/2(n^3 + n^2) I broke it apart for the summation of both, which gave me
1/2 [ (n^4 + 2n^3 + 2n^2)/4 + (2n^3 + 3n^2 + n)/6 ]; which is O(n^4) + O(n^3) = O(n^4). Overkill I guess? Thanks for pointing out a much simpler solution to this problem though. Seriously would have saved me a lot of work >.> (and googling because I didn't know the summation of n^3).


mattman059, that tutorial was pretty good btw. It really helped clarify a bunch of things, so that, along with reading a chapter in my book again seriously helped.

This post has been edited by gnewfenix: 14 Sep, 2009 - 03:38 PM

No problem. Now, even though doing what I did is very simple and lends the correct result, these are still just words. A lot of times you will be required to show all of this stuff mathematically, in which case you would just have to get down and dirty with series and inequalities

Edit: I hope I'm not beating a dead horse here, but let me suggest an easy mathematical way of solving this thing.
First of all, I see that you have already noticed the limits of your last loop - i, 2i, 3i, 4i, ...i^2, because these are the i numbers from 1 to i^2 that are divisible by i itself. Now, here's my suggestion - rewrite your code so that it performs the same number of calculations, but without the annoying if-statement. Here is how the code can be rewritten:



Two things to note:

1. The 2nd loop now goes until i. And that's fine, because that's how many times it actually operates.
2. Now the k goes up to i*j, and that makes sense. The i is fixed, and j iterates from 1 to i, giving us the same pattern.

Now this is a lot easier to calculate Big-O of.

This post has been edited by Neumann: 14 Sep, 2009 - 04:46 PM