Question 1: What is the Big-O running time of the subsequent code fragment?
Assume lst1 has N items, and lst2 has M items.
public static int Count( List lst1, List lst2)
{
Iterator itr1 = lst1.iterator();
int count=0;
while ( itr1.hasNext() )
{
Integer x = itr1.next();
Iterator itr2 = lst2.iterator();
while ( itr2.hasNext() )
if ( x.equals( itr2.next()) )
count++;
}
return count;
}
a. If an ArrayList is passed for lst1 and lst2. Clarify your answer.
b. If a LinkedList is passed for lst1 and lst2. Clarify your answer.
Question 2: What is the Big-O running time of the subsequent code fragment?
Assume lst has N items.
public static int calc( List lst )
{
int count = 0;
int N = lst.size();
for ( int i=0; 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. Describe your answer.
b. If a LinkedList is passed. Describe your answer.