Big O: Nested For Loop With Dependence

Question

I was given a homework assignment with Big O. I'm stuck with nested for loops that are dependent on the previous loop. Here is a changed up version of my homework question, since I really do want to understand it:

sum = 0;
for (i = 0; i < n; i++ 
 for (j = 0; j < i; j++) 
 sum++;

The part that's throwing me off is the j < i part. It seems like it would execute almost like a factorial, but with addition. Any hints would be really appreciated.

• mrk: Nice explanation here

Answer 1

So let me clarify a few things, you are interested in the big-O notation - this means upper bound. In other words, it is okay to count more steps than you actually do. In particular, you can modify the algorithm to

 ...
 for (j = 0; j < n; j++) 
 ...

So you have two nested loops, each loop runs $n$ times, which gives you an upper bound of $O(n^2)$

Of course, you would like to have a good estimate for the upper bound. So for completion, we want to determine a lower bound. This means its okay to count less steps. So consider the modification

for (i = n/2; i < n; i++)
 for (j = 0; j < n/2; j++) 
 sum++;

Here, we perform only a some of the loop-iterations. Again we have two nested loops, but this time we have $n/2$ iterations per loop, which shows that we have at least $n^2/4$ additions. In this case we denote this asymptotic lower bound by $\Omega(n^2)$. Since the lower and upper bound coincide, we can even say that $n^2$ is a tight asymptotic bound, and we write $\Theta(n^2)$.

If you want to know more, read here.

Answer 2

sum = 0;
for (i = 0; i < n; i++)
 for (j = 0; j < i; j++) 
 sum++;

Let's trace this out:

• When i=0, the inner loop will not run at all (0<0 == false).
• When i=1, the inner loop will run once (for j==0).
• When i=2, the inner loop will run twice. (for j==0 and j==1).

This algorithm will thus increment sum the following number of times:

$$\sum_{x=1}^n x-1 = 0+1+2+3+4... + n-1 = \dfrac{n(n-1)}{2}$$

We can see by inspection that the sum is a "triangular number". Distributing $n$ into the rest of the numerator, we arrive at $\dfrac{n^2-n}{2},ドル of which the fastest-growing term is $n^2$ hence the Bachman-Landau Big-Theta complexity is $\theta(n^2) \equiv O(n^2) \ and\ \Omega(n^2)$.

Answer 3

let's see if I can explain this...

So if the inner loop was j

Now, for the first iteration you do n-(n-1) times through the inner loop. on the second time you do n-(n-2) times through the inner loop. On the Nth time you do n-(n-n) times through, which is n times.

if you average the number of times you go through the inner loop it would n/2 times.

So you could say this is O(n*n/2) = O(n^2/2) = O(n^2)

Does that make sense?

• user1000229: It's a little weird, but I think I get it! Thanks! It might take a little time to sink all the way in haha
• user1000229: So if that j < i part was actually j < i^2, the resulting O for that portion would be n^2/2?
• ajon: First of all note that O(n^2/2) = O(n^2). Now if you change it to j<i^2, then you are doing (n-(n-1))^2 on the first iteration and n^2 on the last iteration. I'm not remembering what the big-O notation would be for the inner loop. O(n^2) is a loose upper bound. So a loose upper bound for the whole thing would be O(n^3), but that inner loop is less than O(n^2). Does that make sense?