Reference no: EM131662140

Question: Static method removeEveryOtherItem removes items in even positions (0, 2, 4, etc.) from a List. One possible implementation of removeEveryOtherItem is shown below:

public static void removeEveryOtherItem( List<?> lst)

{

   for( int i = 0; i < lst.size( ); i++ )

         lst.remove( i );

}

a. What is the Big-Oh running time if lst is an ArrayList.

b. What is the Big-Oh running time if lst is a LinkedList.

c. Suppose we have two computers, Machine A and Machine B. Machine B is twice as fast as Machine A. Machine A takes 1 sec. on a 100,000 item list. How large a list can Machine B process in 1 second?

d. Rewrite removeEveryOtherItem, using an iterator, so that it is effi- cient for linked lists and does not use any extra space besides the iterator.