3. You are given an input array A of n positive integers. The integers are not necessarily distinct and you do not know anything about the range of values or the distribution of the integer:s The problem is to rearrange the n integers in A so that the following properties are satisfied o all of the odd input integers precede all of the even input integers, the odd integers are in the same relative order as they were in the input, and the even integers are in the same relative order as they were in the input. Let N denote the number of bits needed to store the input array A. The goal is to design algo- rithms to solve the problem in time that is linear in both n and N with different assumptions about n and N (a) Give a careful description of the model of computation that you are using to analyze the complexity of your algorithms in parts (b) and (c) being especially careful about the inds of operations that you are counting (b) Suppose that n is small enough to fit into a single computer word, and that the value of N does not restrict what your algorithm can do. Design and analyze an algorithm with worst case complexity O(n) O(N) to solve the problem (c) Suppose that the value of N is almost as large as the available memory in your computer leaving only space for auxiliary storage for your algorithm. You may assume that n fits into a single computer word, and that each of the n input integers can fit into a single position of array A (i.e. A[l], A[2], A|3],... can each hold one input integer) but you may not assume that the space allocated to each Ali] is a constant number of bits or words. Your algorithm should have worst case complexity O(n) +cN with cs3