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

equals , shown below, returns true if the two lists have the same size
and contain the same elements in the same order. Assume N is the size
of both lists.

6.10

public boolean equals( List<Integer> lhs, List<Integer> rhs )
{
if( lhs.size( ) != rhs.size( ) )
return false;

for( int i = 0; i < lhs.size( ); i++ )
if( !lhs.get( i ).equals( rhs.get( i ) )
return false;

return true;
}

a. What is the running time of equals when both lists are ArrayList s?

b. What is the running time of equals when both lists are LinkedList s?

c. Suppose it takes 4 seconds to run equals on two equally-sized

10,000-item LinkedList s. How long will it take to run equals on
two equally-sized 50,000-item LinkedList s?

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

all types of lists.

hasSpecial , shown below, returns true if there exists two unique num-
bers in the list that sum to a third number in the list. Assume N is the
size of the list.

6.11

// Returns true if two numbers in c when added together sum
// to a third number in c.
public static boolean hasSpecial( List<Integer> c )
{
for( int i = 0; i < c.size( ); i++ )
for( int j = i + 1; j < c.size( ); j++ )
for( int k = 0; k < c.size( ); k++ )
if( c.get( i ) + c.get( j ) == c.get( k ) )
return true;

return false;
}

a.

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

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

b.

c.

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