x = 0;
for (i = 1; i <= n/2; i ) {
for (j = 1; j <=n; j ) {
if (j > i)
x ;
}
}
I'm trying to predict the value of x by capturing a summation but I'm kind of stuck because I know that for each iteration of the first for loop, the summation changes for the inner loop. For example if we assume x is 10, after the first completion of the inner loop, x would have 9, then after the 2nd completion, we add 8 to x, then 7, 6, etc. The final value of x would be 35. How would I represent this in a cohesive equation for any positive even integer n?
CodePudding user response:
Skip to the end for a simple equation; here I show the steps you might take.
First, here's the original code:
x = 0;
for (i = 1; i <= n/2; i ) {
for (j = 1; j <=n; j ) {
if (j > i)
x ;
}
}
We can start j at i 1 to skip a lot of pointless loops
x = 0;
for (i = 1; i <= n/2; i ) {
for (j = i 1; j <=n; j ) {
if (j > i)
x ;
}
}
Then instead of adding 1 on each of n-i loops, we can just add n-i.
x = 0;
for (i = 1; i <= n/2; i ) {
x = (n-i)
}
That's the same as this (just writing out what we're adding in the loops):
x = (n-1) (n-2) ... (n - n/2)
We can pull out the n's.
x = n * (n/2) - 1 - 2 - 3 - ... - n/2
The final simplification is for the summation of 1 through n/2.
x = n * (n/2) - ((n/2) * (n/2 1))/2