All questions in this sheet must be answered with the demonstrated detailed steps to demonstrate working out the solutions.

QUESTION ONE [25 marks ]

Determine the Big O Notation Algorithmic Complexity for each of the following problems below , showing clearly step by step how you came by your answers.

a. (2n+2)³ / 4n ³ [ 2 marks ]

b. 1/2n * [ (n+4)³ ] [ 2 marks ]

c. n(n+8)(2n +1)²] [ 2 marks ]

d. (n+4) / 2n⁷ [ 2 marks ]

e. [(2n+4)(n +3)²]/n [ 2 marks ]

f. (5n+1)³ / n⁷ [2 marks ]

g. n⁴ +2n⁶ + n [2 marks ]

h. for (i=2; i<4; i+=2){ [2 marks ]

for (j=0; j

sum= sum + 3; } }

i. for (i=0; i

for (j=0; j

A[i] = random(n);

sort(A, n);

}

}

j. sum = 0; [2 marks ]

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

if (is_even(i)) {

for (j = 0; j < n; j++)

sum++;

} else

sum = sum + n;

}

k. List *SearchList(List *a, int key) { // The list has n elements

if (a == NULL)

return NULL; // not found

else if (a->data == key)

return a;

else

return SearchList(a->next, key); [ 2 marks ]

L. int somefunc(int n) {

if (n <= 1)

return 1;

else

return somefunc(n-1) + somefunc(n-1); [2 marks ]

j. Order the functions from part (a) to part(l) from best case to worse case complexity

[ 1 marks ]