1
$\begingroup$

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?

1 Answers 1

1

The summation has $n/2+1$ terms; i=0 is the first term and i=n/2 is the last one! So you should have

summation(n) = (n/2+1) (n+n)/2

and

summation(f(x)) = (n/2+1) (0+n)/2.