The collections api - Data Structures and Problem Solving Using Java - page 284

intersect , shown below, returns the number of elements that are in
both lists. Assume both lists contain N items.

6.12

// Returns the number of elements in both c1 and c2
// Assumes no duplicates in either list.
public static int intersect ( List<Integer> c1, List<Integer> c2 )
{
int count = 0;

for( int i = 0; i < c1.size( ); i++ )
{
int item1 = c1.get( i );
for( int j = 0; j < c2.size( ); j++ )
{
if( c2.get( j ) == item1 )
{
count++;
break;
}
}
}

return count;
}

What is the running time of intersect when both lists are
ArrayList s?

a.

What is the running time of intersect when both lists are
LinkedList s?

b.

Suppose it takes 4 seconds to run intersect on two equally-sized
1,000-item LinkedList s. How long will it take to run intersect on
two equally-sized 3,000-item LinkedList s?

c.

d.

Does rewriting the two loops using the enhanced for loop (i.e.
for( int x : c1 ) ) make intersect more efficient? Provide an
explanation of your reasoning.

containsAll returns true if the first list contains all the elements in the
second list. Assume the lists are approximately the same size and
have about N items each.

6.13