1.  What is the Big-O running time of the following code fragment?


      public static int calc( List<Integer> lst, int N )
      {
         int count = 0;
         for ( int i=0; i<N; i++)
         {
            if (lst.get(i) > 0)
               sum += lst.get(i);
            else
               sum += lst.get(i) * lst.get(i);
         }
         return sum;
      }

   a.  If an ArrayList is passed.  Explain your answer.
   b.  If a LinkedList is passed.  Explain your answer.



2.  What is the Big-O running time of the following code fragment?

   public static void add( List<Integer> lst1, List<Integer> lst2)
   {
      for ( Integer x : lst1 )
         lst2.add(0, x);
   }


   a.  If an ArrayList is passed for lst1 and lst2.  Explain your answer.
   b.  If a LinkedList is passed for lst1 and lst2.  Explain your answer.



3.  What is the Big-O running time of the following code fragment?

   public static int Count( List<Integer> lst1, List<Integer> lst2)
   {
      Iterator<Integer> itr1 = lst1.iterator();

      int count=0;
      while ( itr1.hasNext() )
      {
         Integer x = itr1.next();
         Iterator<Integer> itr2 = lst2.iterator();
         while ( itr2.hasNext() )
            if ( x.equals( itr2.next()) )
               count++;
      }

      return count;
   }


   a.  If an ArrayList is passed for lst1 and lst2.  Explain your answer.
   b.  If a LinkedList is passed for lst1 and lst2.  Explain your answer.