For each of the C functions below, give as tight a worst-case runtime bound as y

Question

For each of the C functions below, give as tight a worst-case runtime bound as you can. Express your answers with Big-O / Big-Theta notation. Show your reasoning.

int E(int a[], int n) { // tricky!
int x=0, i, j;

for(i=0; i<n*n; i++){
     if(i%n == 0)
          for(j=0; j<n; j++)
              x += a[j];
     else
         x--;
}
return x;
}


int F(int a[], int n) {
int x=0, i, j;

for(i=1; i<n; i=i*2){
   for(j=0; j<n; j++)
      x += a[j];
}
return x;
}


int G(int a[], int n) {
int x=0, i, j;

for(i=1; i<n; i=i*2){
    for(j=0; j<i; j++)
        x += a[j];
}
return x;
}

Having trouble with analyzing fuction and expressing in Big O or Big Theta notation. I dont understand tight or worst case.

Explanation / Answer

1)

The first for loop runs n ^ 2 times.

The nested inner loop runs when   i % n == 0. Which means it runs for

i = n, 2n, 3n, ... n ^ 2

So, inner loop runs n times.

Hence, the no of times the function runs can be calculated as

count = ( n^2 - n ) + ( n * n )

We took ( n^2 - n ) as the outer for loop runs n^2 times total. But out of that, n times the inner loop also runs. So, this part represents the number of times the if condition is false.

We took ( n * n ) as the outer loop runs n times when the if condition is true. And the inner loop runs n times each time.

Hence, Time Complexity = O(( n^2 - n ) + ( n * n ) )

                                          = O( n ^ 2 - n + n ^ 2 )

                                          = O( 2 * ( n ^ 2 ) + n )

                                          = O( 2 * ( n ^ 2 ) )    (when n is large, n ^ 2 >> n)

                                          = O( n ^ 2 )

2)

Here the outer loop runs log n times, with log having base 2 as i is doubled with each iteration.

The inner loop runs n times.

Hence, time complexity = O( logn * n )

                                        = O(n logn)

3)

In this function, the outer loop runs logn times with base 2 as with each iteration, the value of i is doubled.

The inner loop runs

                     2 ^ 0 + 2 ^ 1 + 2 ^ 2 + ... + 2 ^ t             times,

where    t = log n

Hence, no of times inner loop runs = 1 * ( 2 ^ ( t + 1) - 1 ) / (2 - 1) =

             (as sum of G.P series = a * (r ^ n - 1) / (r - 1), here n = t + 1, a = 1, r = 2 )

Here, t = log n with base 2

No of time loop runs = 2 * ( 2 ^ t ) - 1 = 2 * (2 ^ logn) - 1 = 2n -1

Hence, time complexity = O(nlogn)

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.