Here is a quick sketch of the solutions.
In grading, I am looking only for a few things on each question,
and an overall understanding of the important concepts.

1. (a) O( N ) because of the single loop, and each get is constant time
   (b) O( N^2 ) because the calls to get are O(N)
   (c) For a quadratic algorithm, when N is increased
       by a factor of 2, the running time increases
       by a factor of 2^2 = 4. So the time will be 8 sec.
   (d) Use an iterator to get an O( N ) algorithm for all types of lists.


2.

   (a)
     public static List<String> emptyLists( Map<String,List<Integer>> m )
     {
         List<String> result = new ArrayList<String>( );

         for( Map.Entry<String,List<Integer>> e : m.entrySet( ) )
             if( e.getValue( ).isEmpty( ) )
                 result.add( e.getKey( ) );

         return result;
     }


   (b)
     The running time is O( N ), where N is the number of map entries.


3.
     public static void mergesort( String [ ] arr, Comparator<String> cmp )
     {
         mergeSort( arr, cmp, 0, arr.length - 1 );
     }

     private static void mergeSort( String [ ] arr, Comparator<String> cmp, int low, int high )
     {
         if( low <  high )
         {
             int mid = ( low + high ) / 2;

             mergesort( arr, cmp, low, mid );
             mergesort( arr, cmp, mid + 1, high );

             merge( arr, cmp, low, high );
         }
     }