ME TEST SERIES

Question

Consider two arrays A[] and B[],if arrays A is in increasing order and array B is in decreasing order is input to join a algorithm. the output is an array C[1......2n] which has all the values of the arrays A[]  and B[] and is increasing order . what is the worst case time complexity for join algorithm to join two array?

A) O(n2)

B)O(n)

C)O(1)

D)O(nlogn)

Answer 1

We can do it in O(n).

It is similar to the MERGE procedure, where we merge two sorted arrays into one sorted array. The difference is that now array B is in reverse order. So, instead of starting indexing B from 0 and incrementing its index whenever we insert an element from B to C, we can start indexing B from n-1, and keep decrementing it whenever we insert an element from B to C, until it reaches 0.

Just some small changes to MERGE procedure will do the work.

Comments

Yes answer will be O(n) Take example

A>>10,20,30,40,50     B>>45,35,25,15,5  compare one by obe and merge them in new array

so therefore O(n)

---

Yes sir total 2n-1 comparison =o(n)

---

Can we do it in this way

First merge theses two arrays as given

After merging first half array already sorted remaining can be sorted using insertion sort in o(n) time

So complexity= o(n)+ o(n)= o(n)

Please verify if I am wrong?