Consider the operation of merging together two reference-based sorted lists, lis

Question

Consider the operation of merging together two reference-based sorted lists, list1 and list2, into a single reference-based sorted list, list3. Suppose list1 is size M, and list2 is sizeN.

a) Suppose you implemented this operation at the application level by using the iteration operations to first obtain each element of list1, adding all of them to list3, and then to obtain each element of list2, also adding all of them to list3. What is the Big-O complexity of this approach? (remember to count the time taken by the lists methods.)

b) Another approach is to implement the operation as a public method merge of the RefSortedList class. The merge method would create and return a new reference-based sorted list that consists of the merger of the current list and an argument list.

public RefSortedList<T> merge (RefSortedList<T> inList)

// Returns a new list consisting of a merge of this list with inList.

Describe an algorithm for implementing this method. What is the Big-O complexity of your algorithm?

c) Discuss the difference between your answers to parts a and b. What can you conclude from the difference?

Explanation / Answer

a)
=> We can Append List1 to List3 by iterating each element of List1. SInce List1 is sorted, we can append all elements to List3 in O(M) where M is the size of List1.
=> on adding elements of List2, we need to take care of thing that after insertion of each element of List 2, the resultant List3 must be sorted. So to find the right position for an element, we need to find the appropriate position for an element. This can be done in O(MN) where M is size of List1 and N is size of List2.
=> Total time complexity is O(M) + O(MN) => O(MN)

b)
int* merge(int* l_1,int m,int* l_2,int n){
   int* res = new int[m+n];
   int i = 0; int j = 0; int k = 0;
   while (i < m && j < n){
       if (l_1[i] < l_2[j]){
           res[k] = l_1[i];
           k += 1;
           i += 1;
       }
       else{
           res[k] = l_2[j];
           k += 1;
           j += 1;
       }
   }
   while (i < m){
       res[k] = l_1[i];
       k += 1;
       i += 1;
   }
   while (j < n){
       res[k] = l_2[j];
       k += 1;      
       j += 1;
   }
   return res;
}

Big-O complexity of your algorithm => O(M+N);

let l_1 = [2,3,7]; i = 0;
l_2 = [1,6];   j = 0;
l_3 = [];

we will start from 0 index of both list and increase the index of the list from which we have picked an element to insert it into list_3, our insertion is O(1) and we are iterating each element of l_1 and l_2 so total time complexity is O(M+N);

Step 1:
l_1 = [2,3,7];    i = 0;
l_2 = [1,6];   j = 1;
l_3 = [1];

Step 2:
l_1 = [2,3,7];    i = 1;
l_2 = [1,6];   j = 1;
l_3 = [1,2];

Step 3:
l_1 = [2,3,7];    i = 2;
l_2 = [1,6];   j = 1;
l_3 = [1,2,3];

Step 4:
l_1 = [2,3,7];    i = 2;
l_2 = [1,6];   j = 2;
l_3 = [1,2,3,6];

Step 5:
l_1 = [2,3,7];    i = 3;
l_2 = [1,6];   j = 2;
l_3 = [1,2,3,6,7];

Step 6:
return l_3;

=> Second method is best as we have better time complexity in such case

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.