Consider the code below that removes duplicate integers from a list of integers.
ID: 3857307 • Letter: C
Question
Consider the code below that removes duplicate integers from a list of integers. Evaluate the number of operations taken by this code under the assumption that every declaration, assignment, check, negation, subtraction, and LinkedList method takes exactly 1 operation, except contains which we assume uses linear search and thus takes k operations where k is the size of the LinkedList being searched. List removeDuplicates (List dups) { List newList = new Linkedlist (): while (!dups.isEmpty()) if (!newList.contains (dups.get (dups.size() -1)) { newList add (dups.get (dups.size() - 1)): } dups.remove (dups.size()-1): } }Explanation / Answer
Let's understand the code and the number of operations inside it...:
First of all, what's happening in the code is that we are given a function which is passed with a linked list that contains all the elements. Inside the function, we are creating a new (duplicate-free) linked list that contains all the non-duplicate elements of the passed linked list. we are reading every element in the first linked list and before adding to the new list, we are checking if the new list already contains this element or not. If it doesn't, we add it to the new list, and if it doesn't, we don't add it. Now let's have a look at all the operations happening inside the function.
The first statement is :
List newList = new LinkedList();
The above statement is a combination of declaration and assignment operations. Thus, it's weight is 2 (Lets compute it with "weight").
The next statement is a while loop.
while(!dups.isEmpty()){
The while loop will check on every element in the dups list. Thus, if there are k elements inside the list, the condition inside the paranthesis of while clause will be checked for (k+1) times. How? after running for the kth element, the condition will be checked once again where the list would be found empty and the while loop ends.
So the operation (!dups.isEmpty()) is a combination of check (isEmpty() method of the list) and a negate (!) operation. And since it will run for (k+1) times, total weight of this statement becomes: (k+1) x 2 = (2k + 2)
The next statement is an if condition which resides inside the while loop. Please note here that while the condition inside the while paranthesis run for (k+1) times, the statements inside the body of the while loop runs for only k times only(as it wouldnt be executed for the termination condition). The statement is:
if(!newList.contains(dups.get(dups.size()-1))) {
The above statement contains 2 methods for dups list (dups.size() & dups.get() ), 1 subtraction operation (dups.size() - 1 ), 1 check method for newList (newList.contains() ) and 1 negate operation (!). So the number of operations become 5. Since this if condition is checked for every element of dups list, it runs for k times, thus, the total weight for this statement becomes 5k.
The next statement is inside the body of if condtion:
newList.add(dups.get(dups.size()-1)); }
The number of operations in this statement is somethin like this: 2 methods for dups list ( dups.get() & dups.size() ), 1 subtraction operation ( dups.size() - 1 ) and 1 method for newList list ( newList.add() ). So the number of operations become 4. The weight of this statement depends on how many times the if statement returns true and that can vary with the values inside the dups list. We'll see example for this later in this answer.
The final statement is:
dups.remove(dups.size() - 1) ; } }
This statement has 2 methods of dups list ( dups.remove() & dups.size() ) and 1 subtract operation ( dups.size() - 1 ). So the number of operations become 3. Also this statement runs for every element of dups list, so the weight of this statement becomes 3k.
In the worst case (where every element in the dups list is different from each other):
In this case, the statement inside the if block would run for k times as there are no duplicates and so every encountered element would have to be added to the newList. Thus the weight for that statement would become 4k.
Total weight of the function becomes :
2 + (2k + 2) + 5k + 4k + 3k = (14k + 2)
So, for example, if there are 4 elements in the dups list, then the total number of operations = (14 x 4) + 2 = 58 operations
In the best case (when every element in the dups list is same) :
In this case, the statement inside the if block would run for 1 time only (for the first element only) as for the rest of the elements it wouldn't be executed (Why? We already discussed at the start of this answer while I explained about the working of this code) . So the weight for this statement would be 4.
Now, the total weight of the function becomes:
2 + (2k + 2) + 5k + 4 + 3k = (10k + 6)
So, for example, if we have 4 elements inside the dups list, all of them being exacty same, total number of operations become:
(10 x 4 ) + 6 = 46
Hope this helps...
BEST WISHES!