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.