Determine Running Time

$15.00

Category:

Description

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);