Loop body execution times

[scuzzo]

I need help in analyzing loop structures. I am a student and need to know this for a class.
In my first example here:
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
I need to figure out how to analyze that this loop runs n^2 times. (This was an example given in a later class is the only reason I know that much). The instructor wants for us to set up a table as such:

i _____ j _____ # of reps
1 _____ n _____ n
2 _____ n _____ n
3 _____ n _____ n

Another example is this:
for (int i=1;i<=n;i++)
for (int j=1;j<=i;j++)
According to the instructor the table should look like

i _____ j _____ # of reps
1 _____ 1->1 _____ 1
2 _____ 1->2 _____ 2
3 _____ 1->3 _____ 3

and from that table I am supposed to be able to infer that (n(n-1))/2.
Can anyone give me an answer that sounds like it is in plain English or give me some terms to search in Google. I have tried very hard to find this subject using multiple search engines and am comming up empty. Thanks for any help.

[Rashakil Fol]

I hate dumb instructors.

I would just add up how many times the very inside part executes.

In the first example, the inner loop executes its inside n times each time it's run, and the inner loop gets run n times. So the inside of the inner loop gets run n*n times. Easy, right?

In the second example, the very inside of the inner loop gets hit 1 time the first time the inner loop runs, then 2 times the second time the inner loop runs, and then 3 times, and then 4 times, and so on, until the last time it's run, it runs n times, for whatever value n is.

Adding those numbers up, we see that the very inside is hit this many times:

1 + 2 + 3 + 4 + ... + (n-2) + (n-1) + n

What's that sum? Using pure *math*, we can find that the expression adds up to n(n+1)/2.

And so the inner loop gets run n(n+1)/2 times. It looks like your professor (who said n(n-1)/2) was wrong.

(So how do you find that the sum of the first n positive integers is n(n+1)/2? There are many ways. One way is to pick the points (1,1), (2,3), (3,6) and find what parabola fits it by solving the equations ax^2+bx+c = y, where (x,y) are the constants (1,1), (2,3), and (3,6) in the three equations, and a, b, and c are the variables we're solving for. We find that a=1/2, b = 1/2, and c=0. To know this method works, you'd have to have some way of knowing that the parabola that fits the first three points would definitely fit the rest of the curve.

The general trick here is to just memorize that 1+2+...+n = n(n+1)/2. It's such a commonly used formula that you should just get used to it. Similarly, it's useful to know that 1^2+2^2+...+n^2 = n(n+1)(2n+1)/6. And 1^3+2^3+...+n^3 = [n(n+1)/2]^2. It's no accident that the sum of the first n squares gives a cubic expression and the sum of the first n cubes gives a quartic expression.

It's also useful to get used to getting a feel of how the orders of growth of these things are, without needing an exact formula, by taking samples and just looking at things. For example, it should eventually become instinctual that if an inner loop gets run n times and its cost grows from f(1) to f(n), then the total cost is going to be on the order of n*f(n), and if it's better, you have to prove it. (It's only "better" when f(n) grows faster than any polynomial, anyhow.) You might wonder, why should this be instinctual? Well, if you're going to run something n times, its cost is going to better than n multiplied by its worst case cost. Duhhhhhhhh.)

[scuzzo]

How do I analyze
for (int i = 1; i <= n; i=2*i)

for (int j = 1; j <= n; j++)

[Rashakil Fol]

Very carefully.

[BestJewSinceJC]

How do I analyze
for (int i = 1; i <= n; i=2*i)

for (int j = 1; j <= n; j++)

It's pretty easy. The second loop obviously runs O(n) and as a hint for the first loop, pick some arbitrary values for n, then write out how many times it is going to run for that value of n. You obviously have to multiply these two values since the one loop is nested in the other...

[laehc]

Here's an easy way to get:
1 + 2 + 3 + ... + n = n(n+1)/2

Taking n=6, write the sum underneath in reverse order, and add each column like this:

1 + 2 + 3 + 4 + 5 + 6
6 + 5 + 4 + 3 + 2 + 1
_________________
7 + 7 + 7 + 7 + 7 + 7

That gives the sum of six 7s, or 6 x 7 =42 (which is n(n+1) for n=6).
Each row is equal so divide the 42 by 2 and you get:

1 + 2 + 3 + 4 + 5 + 6 = 21

The mathematician Gauss is supposed to have worked that out when he was a kid and his teacher told the class to add every number from 1 to 100, so he could have a nap.