Thread: Some Big-O problems

I would really appreciate it if someone would verify that these solutions are correct, I am supposed to find the Big O of the code fragment:

Code:

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. (get operations are O(1) for ArrayList)
O(N^2)

b. If a LinkedList is passed. (get operations are O(N) for LinkedList)
O(N^4), confused by this one, because I do not know whether to count
both 1st.get line in the else statements as O(N) and multiply; this is
what I did.


Next problem:

Code:

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.
According to my book, an enhanced for loop makes the running time O(N) for any list, becuase the iterator will efficiently advance from one item to the next, so I assume this is O(N)?

b. b. If a LinkedList is passed for lst1 and lst2.
I presume the answer is the same as for part a, because it says O(N) running time for ANY list structure with an enhanced for loop.

Last Problem: (Too big to put in code block format)

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.

For both of these, I got O(N) for the first while loop times O(N) for the second while loop times O(N) for the if loop, for a total of O(N^3). I know this cannot be right, as there has to be more to the problem than this. Maybe the count operation takes O(N) for the arrayList instead of constant time because the array may shift?