I'm using C language*
Question 1 – Determine Running Time: 8 marks

For each of the following code fragments determine the worst-case O notation running time and briefly justify your answer. In each case your answer should be a function of n. If the question refers to an array you can assume that the size of that array is n. Note that you are not expected to derive a detailed cost function, just the Big O notation running time.

 

Example

for (i = 1; i <= n; i++) {  

    sum = sum + i;

}

 

Answer: The loop body runs in O(1) and the loop is executed O(n) times. Total running time is O(1)×O(n)=O(n).

 

a

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

      for (int j = 0; j < 3; j++) {

         for (int k = 0; k < 3; k++) {

            printf("%d", arr[i]);

           }

         printf("n");

      }

}

 

b

for (int i = 2; i <= n; i++) {

      int j;

      printf("n%d:", i);

      for(j = 2; j <= i; j = j * 2){

         printf("%d ", j);

      }

      printf("n%d:", i);

      for(int k = j/2; k >= 2; k = k / 2){

         printf("%d ", k);

      }

}

 

c

int i = 0;

int j = 0;

while(i < n){

      while(j < n){

         printf("{%d,%d}",arr[i],arr[j]);

         j++;

      }

      i++;

      j = 0;

      printf("n");

}

 

d

int result = 0;

int i = 0;

while (i < n / 2){

      result += arr[i];

      i += 1;

      while (i >= n / 2 && i < n){

         result += arr[i];

         i += 1;

      }

}

printf("%dn", result);