Let A and B be two sorted arrays, each with n elements. For the purposes of this problem, assume that all 2n elements are distinct integers, and assumen= 2k + 1 for some integer k ≥ 1. In this problem, we wish to compute themedianof the 2nelements, which will be the average of the nth and (n+ 1)th smallest elements in the (combined) array.
For example, suppose A= [1,2,4,8,16,32,64,128,256] and B= [30,40,50,60,70,80,90,100,110]. If we merge the arrays and sort it, we get C= [1,2,4,8,16,30,32,40,50,60,64,70,80,90,100,110,128,256]. From this we see that the middle two elements are 50 and 60 and so the median is 55.
- Consider the following algorithm: merge the two arrays and sort it to produce a new array C with 2n elements. Then the median must be (C[n] +C[n+ 1])/2. Determine whether this algorithm is linear or linearithmic. Clearly justify your answer.