Running Times on Linked List and Array Data Structures

[ronnie30]

I'm trying to find the Big O for each of these code fragments, for an ArrayList and a Linked List:

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;
      }

I think it is O(N) for an arrayList and O(N^3) for a linked list; though I am unsure if both calls to lst.get in the else loop count as O(N) each.

Another:

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

Since there is an enhanced for loop, which efficiently moves from one item to the next, I think it is O(N^2) for an arryList and O(N) for a linked list.

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

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

      return count;
   }

I am confused about the hasNext function; I assume that for array and linkedList, the running time is O(N^2) because of the two nested while loops.