Algorithm:
for (int i = 0; i < 2*n; i += 2) for (int j = n; j >i; j--) foo();
I want to find the number of times foo() is called.
# of foo() calls for the second loop as i changes: 1st loop: n - 0 2nd loop: n - 2 3rd loop: n - 4 nth loop: n - f(x); f(x) = last term +2; where f(0) = 0 Total # calls = Summation(n - f(x)) from [i = 0] to [i = n/2 (where f(x) == n)] = Summation(n) - summation(f(x)) = (n/2)(n+n)/2 - (n/2)(0 + n)/2 = n^2/2 - n^2/4 = n^2/4
I've done all the work but my equation always gives values that are a bit off.
What have I done wrong?