Complexity

Question

Consider X[1, ..., n] and Y[1, ..., n] be two arrays each containing n-numbers both of which are already sorted. What is the time complexity to find median by combining the two arrays?

• O(log n)
• O(n)
• O(n log n)
• O(log log n)

Comments

Can you tell me how did you copied stuff from made easy website?

Answer 1

Ans. O(log n)

Let me solve it using example

There are 2 arrays:-

ar1[] = {1, 12, 15, 26, 38},  ar2[] = {2, 13, 17, 30, 45}

For above two arrays m1 = 15 and m2 = 17

For the above ar1[] and ar2[], m1 is smaller than m2. So median is present in one of the following two sub-arrays.

[15, 26, 38] and [2, 13, 17]

Let us repeat the process for above two sub-arrays:

 m1 = 26, m2 = 13.

m1 is greater than m2. So the sub-arrays become

[15, 26] and [13, 17]

Now size is 2, so

median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
       = (max(15, 13) + min(26, 17))/2 
       = (15 + 17)/2
       = 16

So, total complexity = 2*O(log n) + O(1) = O(log n)

Comments

Great Explanation.

Some more examples and code implementation if someone wants to read something extra:

Median of Two Sorted Arrays (enjoyalgorithms.com)

Answer 2

Using simple merging and counting, we get O(n). 

O(log n) can be achieved by comparing the medians of two arrays. (say arr1[] and arr2[])

Algorithm:

1) Calculate the medians m1 and m2 of the input arrays arr1[] and arr2[] respectively.
2) If m1 and m2 both are equal then we are done.
     return m1 (or m2)
3) If m1 is greater than m2, then median is present in one of the below two subarrays.
    a)  From first element of arr1 to m1 (arr1[0...n/2])
    b)  From m2 to last element of arr2  (arr2[n/2...n-1])
4) If m2 is greater than m1, then median is present in one of the below two subarrays.
   a)  From m1 to last element of arr1  (arr1[n/2...n-1])
   b)  From first element of arr2 to m2 (arr2[0...n/2])
5) Repeat the above process until size of both the subarrays becomes 2.
6) If size of the two arrays is 2 then use below formula to get the median.
    Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2

So, using this divide and conquer strategy, each time the array sizes are halved.

Hence, complexity is O(log n).