Java problem!!

You will consider several algorithms which use the methods of java.util.List, giving the algorithmic efficiency and a brief description of the reason. The algorithms are encoded in standard Java methods which have a java.util.List parameter. The analysis shall consider what the Big-O for the method will be when passed an instance of java.util.ArrayList and when passed an instance of java.util.LinkedList.

Analyze the following 6 methods: sum_getImple sum_iteratorImpl removeEvens_getImple removeEvens_iteratorImple double_getImple double_iteratorImple

Each of these methods takes an Integer List as a parameter. There are three tasks implemented by these methods:

Sum the elements of the list Returns the calculated sum Remove the even elements from the list Makes the change within the List argument Double the value of each of the elements within the list Makes the change within the List argument

All three of these tasks involve visiting each element of the list. There are two different implementations for each of these tasks:

One which uses the get method in a for loop to access the elements of the list One which uses an Iterator object in a while loop to access the elements of the list

This difference in implementation is reflected in the name of the method by the suffix: _getImple or _iteratorImple.

For each of the six methods:

Determine the Big-O for the method when passed an ArrayList object and briefly describe the reasoning behind your answer

Determine the Big-O for the method when passed a LinkedList object and briefly describe the reasoning behind your answer

1. The sum_getImple Method

/** * Get the total of the values in an integer list * @param nums The list of integers * @return The sum of the values */ public int sum_getImple(java.util.List nums) { int total = 0; for(int i = 0; i < nums.size(); i++) { total += nums.get(i); } return total; }

2. The sum_iteratorImple Method

/** * Get the total of the values in an integer list * @param nums The list of integers * @return The sum of the values */ public int sum_iteratorImple(java.util.List nums) { int total = 0; java.util.Iterator it = nums.iterator(); while(it.hasNext()) { total += it.next(); } return total; }

3. The removeEvens_getImple Method

/** * Remove the even values from a list of integers. * The method modifies the parameter list. * @param nums The list of integers */ public void removeEvens_getImple(java.util.List nums) { for(int i = 0; i < nums.size(); i++) { if(nums.get(i) % 2 == 0) { nums.remove(i); } } }

4. The removeEvens_iteratorImple Method

/** * Remove the even values from a list of integers. * The method modifies the parameter list. * @param nums The list of integers */ public void removeEvens_iteratorImple(java.util.List nums) { java.util.Iterator it = nums.iterator(); while(it.hasNext()) { int value = it.next(); if(value % 2 == 0) { it.remove(); } } }

5. The double_getImple Method

/** * Double the values in a list of integers. * This method modifies the parameter list. * @param nums The list of integers */ public void double_getImple(java.util.List nums) { for(int i = 0; i < nums.size(); i++) { int value = nums.get(i); nums.set(i, 2 * value); } }

6. The double_iteratorImple Method

/** * Double the values in a list of integers. * This method modifies the parameter list. * @param nums The list of integers */ public void double_iteratorImple(java.util.List nums) { java.util.ListIterator it = nums.listIterator(); while(it.hasNext()) { int value = it.next(); it.set(2 * value); } }

=============================================

Format of your answers should like this. Don't forget to explain!

When nums is an ArrayList, the sum_getImple method is O( When nums is an LinkedList, the sum_getImple method is O( When nums is an ArrayList, the sum_iteratorImple method is O( When nums is an LinkedList, the sum_iteratorImple method is O(

..... ============================================== Here is the example and sample solution:

/** * Add two elements of a list of Integers * @param nums The list of integers * @param index1 The first index value * @param index2 The secdond index value * @return The sum of the two elements * @throws IllegalArgumentException when index values * are out of range */ public int addTwo(java.util.List nums, int index1, int index2) { if(index1 < 0 || index1 >= nums.size() || index2 < 0 || index2 >= nums.size()) { String msg = "Index value out of range"; throw new IllegalArgumentException(msg); } return nums.get(index1) + nums.get(index2); }

The Sample Solution:

When nums is an ArrayList, the addTwo method is O(k), constant time. This is because the get method of ArrayList takes constant time. The size of the list does not have an effect on the time it takes to access a given element of the list; accessing any element in an array takes the same amount of time.

When nums is a LinkedList, the addTwo method is O(N), linear time. This is because the get method of LinkedList takes linear time. The larger the list, the longer time it make take to access a given element, since finding the n-th element requires handling n-1 linked elements.