The first scenario we consider is inspired by RAID 0 . In this scenario we start with an array A of length N storing non-negative integers, and create two new arrays where the first array stores the values A[i] where i is an even number, and the second array stores the values A[j] where j is an odd number. The following diagram shows this scenario: There are now two new arrays, A1 and A2, are created and the values at even-numbered indices of A are copied to A1, and the values at odd-numbered indices are copied to A2. The idea is now that instead of storing A, we store two separate arrays in a distributed manner. However, if we want to search the array A for particular values, we now need to search these two arrays and then relate the indices back to the original array. The next two tasks together give such a method to search the two arrays in this scenario. Task 1: Consider the following pseudocode function that describes the R0 Search algorithm: In this pseudocode floor (x) and ceiling (x) are the mathematical functions that, respectively, give the largest integer smaller than or equal to x and give the smallest integer larger than or equal to x. You may assume that calculating the floor (x) and ceiling (x) takes constant time. For this algorithm address the following: 1. Identify, and describe very briefly in words, the best-case inputs and the worst-case inputs. Recall that there are four inputs to R0. [ 8 marks] 2. An expression for both the worst-case and best-case running times (or execution time) T(N), and describe the method by which you arrive at this expression. [ 8 marks] 3. The growth function of the worst-case and best-case running times T(N), i.e. a function that does not include constants or low-order terms, e.g. if f(N)=5N+2, then the growth function is N. [5 marks] 4. The Theta notation for the worst-case and best-case running times T(N). In particular, find a set of constants c1,c2 and m0 for which T(N) is (g(N)). [6 marks]