Question 3 [15 Marks] (i) Distinguish between sequential search and binary search applied to an array of n sorted elements. What is the worst-case scenario for both algorithms and what is the resulting runtime complexity? Explain your answers. [3]

(ii) What is meant by Dynamic Programming? Using appropriate diagrams and code snippets, show how the recursive calculation of the Fibonacci sequence f(n) with f(0) = 0; f(1) = 1; f(n) = f(n-1) + f(n-2) can be greatly improved when the dynamic programming approach is applied. [6]

(iii)Assume you need to sort an array of n strings. Each string is between one and eight characters long and consists of capital letters (A to Z) only. Show how Radix sort can be adopted for this task and explain how the algorithm works. Use appropriate diagrams and/or code to support your answer. [6]