3. THE FIRST PART: THE RO SEARCH ALGORITHM 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[1] where 1 is an even number, and the second array stores the values A[J] where f 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 Ro Search algorithm: In this pseudocode floor (x) and celling (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 Re. [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 funning times T(N). In particular, find a set of constants cl,c2 and mD for which T(N) is (E(N]). [6 marks]