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

public static boolean containsAll( List<Integer> bigger,
List<Integer> items )
{
outer:
for( int i = 0; i < bigger.size( ); i++ )
{
Integer itemToFind = bigger.get( i );

for( int j = 0; j < items.size( ); j++ )
if( items.get( j ).equals( itemToFind ) ) // match
continue outer;

// If we get here, no entry in items matches bigger.get(i)
return false;
}
return true;
}

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

a.

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

b.

Suppose it takes 10 seconds to run containsAll on two equally-valued
1000-item ArrayList s. How long will it take to run containsAll on
two equally-valued 2000-item ArrayList s?

c.

d. Explain in one sentence how to make the algorithm efficient for all

types of lists.

containsSum , shown below, returns true if there exists two unique
numbers in the list that sum to K . Assume N is the size of the list.

6.14

public static boolean containsSum( List<Integer> lst, int K )
{
for( int i = 0; i < lst.size( ); i++ )
for( int j = i + 1; j < lst.size( ); j++ )
if( lst.get( i ) + lst.get( j ) == K )
return true;

return false;
}

a.

What is the running time of containsSum when the list is an ArrayList ?

What is the running time of containsSum when the list is a
LinkedList ?

b.

Suppose it takes 2 seconds to run containsSum on a 1,000-item
ArrayList . How long will it take to run containsSum on a 3,000-item
ArrayList ? You may assume containsSum returns false in both cases.

c.