Sorting time complexity


#1

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[] andB[] and is increasing order . what is the worst case time complexity for join algorith to join two array?

A) O(n^2)

B)O(n)

C)O(1)

D)O(nlogn)


#2

Option B

EXAMPLE:

A = [1, 3, 5, 7, 9]
B = [10, 8, 6, 4, 2]
C = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

START TRAVERSING ‘A’ FROM INDEX “0 TO N1” AND FOR ‘B’ FROM “N2 TO 0”
THEN TIME COMLEXITY WILL BE O(N1 + N2)

THIS IS SIMILAR TO WHAT WE DO TO MERGE IN MERGE SORT, ONLY DIFFERENCE IS THAT EITHER BOTH THE ARRAYS ARE SORTED IN ASCENDING OR DESCENDING ORDER.


#3

Though Anmol explained it in abstarct,I want to explain it more intuitively.
Where you think the smallest element can be ?
Since the array 1 is in increasing order,so a[0] is lowest
but for array 2,b[n] will be the lowest element,
so there are two contendors for lowest element - a[0] or b[n]
,we make a comparision and find the smallest and increase the counter of corresponding array and then we again compare like in merge sort.

Complexity we comparing 2n elements so 0(n)


#4

It is just like merging of two sorted lists in merge sort.
algorithm is like this…

k=0,l=n2-1
for(i = 0 ;k<n1 && l>=0 && i<n1+n2 ) //here n1 is list1 size n2 is list2 size.
      if a[k]<=b[l]
             c[i]=a[k];
             k++;
      else
             c[i]=b[l];
             l--;

for(;k<n1;k++)
c[i++]=a[k];

for(;l>=0;l--)
c[i++]=b[l];

So here time complexity is (2*n) = O(n) ( n1=n2)