Assuming that n is a positive even integer, what will be the value of x right after this segment of code is run?

user_16862762 0
Viewed 81
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?

analysis math algorithm
1 Answers

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
user_20410770
Related