Consider the following Algorithm to compare two lists.

Question

Consider the following Algorithm is to compare two lists.

compare list ( list 1, list 2)
{
       for num in list 1
           { 
                 if num not in list 2 
                   return 0 ;
                else
                   remove the first occurrence of num from list 2
           }
                 if list 2 is empty 
 return 1;
}

Let n be the length of list 1 and m be the length of list 2. What is the worst – case running time of given algorithm?

1.   O(n2)
2.   O(m2)
3.   O( m log n)
4.   O(nm)

Comments

according to me,answwer should be O(m²) because suppose 

L1 = 1,2,3,4,5

L2 =1,2,3,4,5

then in each iteration m decreases by 1.as the element is removed

so m + m-1 +m-2 + m-3 + ......= O(m²)

but answer given is O(nm)

correct me pls

Answer 1

time complexity is O(mn)

n element of list1 is searched m times

Comments

but size of list2 is decreasing in every iteration..

---

yes one is reducing each time but one is always fix

---

which is firxed?

see,for first element of list 1 ,we have m elements to cpmare..if first element itself is not found in first iteration,then we return from the function and no further checking.

.and if found, we delete it.deleeting will take O(m) time at max.

next,if first element is found,we check for second element with (m-1) elements.if found we,delete it.deletion will take O(m-1) time here.

for third element,we have m-2) numbers left and so on.........

so,total number of comparisons are m+ (m-1) +(m-2).....=O(m^2)

take any case,,m=n,m<n or m >n.

you ill get O(m²) only