Question

Consider the following function:

int counter( int n)

{ int s = 0;

   for ( int i = 0; i < n; i++)

            for ( int j = i; j > 0; j--)

                       s = s + 1;

  return s;

}

Part (a): How many times "s=s+1;" will be executed? Determine a precise count.  Show all your work.

Part (b): What is the time complexity of the "counter" function in terms of Big-O notation? Justify and show all your work.

Answer 1

Solution:

===============

Here for ( int i = 0; i < n; i++) will be executed exactly n time from i=0 to i=n-1

for each value of i inner for ( int j = i; j > 0; j--) will be executed i times.

thus s=s+1 will be executed in the following way

when i=0 inner for loop will execute 0 times

when i=1 inner for loop will execute 1 times

when i=2 inner for loop will execute 2 times

when i=3 inner for loop will execute 3 times

-----------------

--------------

-------------

when i=n-1 inner for loop will execute n-1 times

Hence total number of times  s = s + 1; will be executed is 0+1+2+3+4+5+6...........(n-1)

This sum is in AP thus its sum is gievn by   = n/2(2a+ (n-1)d)

here a is 0

d is 1

n is n-1

Hence sum is

Ans

Part b) TIme complexity of this function depends on how many times  s = s + 1; statement is executed from above result number of times statement is executed is (n)(n-1)/2 = (n^2-n)/2 Here leading term is n^2 for very large value of n effect of (n)/2 can be neglacted thus time Complexity is given by