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?
