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)

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)

Dark Mode

462 views

4 votes

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)

A) O(n2)

B)O(n)

C)O(1)

D)O(nlogn)

3 votes

Best answer

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.

0