edited by
625 views
4 votes
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)
edited by

1 Answer

Best answer
3 votes
3 votes

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.

selected by

Related questions

1 votes
1 votes
1 answer
3
1 votes
1 votes
1 answer
4